Digraphs: Theory, Algorithms and Applications (Google eBook)
Substantially revised, reorganised and updated, the second edition now comprises eighteen chapters, carefully arranged in a straightforward and logical manner, with many new results and open problems. As well as covering the theoretical aspects of the subject, with detailed proofs of many important results, the authors present a number of algorithms, and whole chapters are devoted to topics such as branchings, feedback arc and vertex sets, connectivity augmentations, sparse subdigraphs with prescribed connectivity, and also packing, covering and decompositions of digraphs. Throughout the book, there is a strong focus on applications which include quantum mechanics, bioinformatics, embedded computing, and the travelling salesman problem. Detailed indices and topic-oriented chapters ease navigation, and more than 650 exercises, 170 figures and 150 open problems are included to help immerse the reader in all aspects of the subject.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Classes of Digraphs
Flows in Networks
Connectivity of Digraphs
Hamiltonian Longest and VertexCheapest Paths and Cycles
Restricted Hamiltonian Paths and Cycles
Paths and Cycles of Prescribed Lengths
Packings Coverings and Decompositions
Feedback Sets and Vertex Orderings
Applications of Digraphs and EdgeColoured Graphs
Algorithms and Their Complexity
2-cycle 2-edge-coloured 2-linkage acyclic digraph arbitrary arc set arc-disjoint assume Bang-Jensen bipartite graph colour complete digraph conjecture consider contains Corollary cycle factor cycle of length decomposition deﬁned deﬁnition deleting denote diﬀerent diﬃcult digraph D directed multigraph directed pseudograph distinct vertices edges eulerian Exercise exists feasible ﬂow feedback arc set feedback vertex set Figure ﬁnd ﬁnite ﬁrst ﬁxed ﬂow following result graph G Gutin Hamilton cycle hamiltonian cycle hamiltonian path Hence implies in-degree integer k-arc-strong k-strong least Lemma Let G line digraph locally semicomplete digraph matroid maximum minimum cost minimum number mixed graph NP-complete NP-hard number of arcs number of vertices obtain one-way pairs optimal oriented graph out-branching out-degree pair polynomial algorithm proof of Theorem Proposition proved the following pseudograph quasi-transitive digraph satisﬁes Section semicomplete multipartite digraph spanning subdigraph strong components strong digraph subgraph subset Suppose Thomassen tournament UG(D undirected graph vertex set weight