Vor Ort
Merkzettel Warenkorb
Produktbild: Digraphs

Digraphs Theory, Algorithms and Applications

Aus der Reihe Springer Monographs in Mathematics

90,94 €

inkl. gesetzl. MwSt.

Beschreibung

Produktdetails

Format

PDF

Kopierschutz

Nein

Family Sharing

Nein

Text-to-Speech

Nein

Erscheinungsdatum

17.12.2008

Verlag

Springer London

Seitenzahl

795 (Printausgabe)

Dateigröße

5982 KB

Auflage

2nd ed. 2009

Sprache

Englisch

EAN

9781848009981

Beschreibung

Rezension

From the reviews:

"Digraphs (directed graphs) are a long-standing and important field of graph theory. Nevertheless, this is the first comprehensive monograph devoted to the subject. As a handbook, it addresses various groups of readers (students as well as researchers, and from various areas of applications). Throughout, because of their importance for applications, emphasis is on algorithms (in form of constructive proofs whenever possible). … a valuable and indispensable reference for many years to come. Readers and users will be thankful!" (P. Schmitt, Monatshefte für Mathematik, Vol. 141 (1), 2004)

From the reviews of the second edition:

"This is a very comprehensive volume on directed graphs and related topics. … an excellent reference. … the book will be useful not just for researchers focusing on digraphs, but also for everyone … . an extensive list of conjectures and open questions is included in every chapter. These are typically very well presented and easy to understand." (Miklós Bóna, MAA Online, February, 2009)

“The first edition of this book was published in 2000 … . The area has continued to develop and this reorganized and updated edition contains an additional six chapters … . there is a strong emphasis on algorithms, and constructive proofs are given whenever possible. There are more than 650 exercises and 150 open problems and conjectures. … the bibliography contains 934 items and the author index contains 740 names. This book would be a valuable resource for anyone interested in digraphs and their applications.” (J. W. Moon, Zentralblatt MATH, Vol. 1170, 2009)

Produktdetails

Format

PDF

eBooks im PDF-Format haben eine festgelegte Seitengröße und eignen sich daher nur bedingt zum Lesen auf einem tolino eReader oder Smartphone. Für den vollen Lesegenuss empfehlen wir Ihnen bei PDF-eBooks die Verwendung eines Tablets oder Computers.

Kopierschutz

Nein

Dieses eBook können Sie uneingeschränkt auf allen Geräten der tolino Familie, allen sonstigen eReadern und am PC lesen. Das eBook ist nicht kopiergeschützt und kann ein personalisiertes Wasserzeichen enthalten. Weitere Hinweise zum Lesen von eBooks mit einem personalisierten Wasserzeichen finden Sie unter Hilfe/Downloads.

Family Sharing

Nein

Mit Family Sharing können Sie eBooks innerhalb Ihrer Familie (max. sechs Mitglieder im gleichen Haushalt) teilen. Sie entscheiden selbst, welches Buch Sie mit welchem Familienmitglied teilen möchten. Auch das parallele Lesen durch verschiedene Familienmitglieder ist durch Family Sharing möglich. Um eBooks zu teilen oder geteilt zu bekommen, muss jedes Familienmitglied ein Konto bei Thalia oder einem anderen tolino-Buchhändler haben. Weitere Informationen finden Sie unter Hilfe/Family-Sharing.

Text-to-Speech

Nein

Bedeutet Ihnen Stimme mehr als Text? Mit der Funktion Text-to-Speech können Sie sich im tolino webReader und in der aktuellen Thalia – Lesen & Hören App das eBook vorlesen lassen. Weitere Informationen finden Sie unter Hilfe/Text-to-Speech.

Barrierefreiheit
  • keine Information zur Barrierefreiheit bekannt

Erscheinungsdatum

17.12.2008

Verlag

Springer London

Seitenzahl

795 (Printausgabe)

Dateigröße

5982 KB

Auflage

2nd ed. 2009

Sprache

Englisch

EAN

9781848009981

Noch keine Bewertungen vorhanden

Verfassen Sie die erste Bewertung zu diesem Artikel

Helfen Sie anderen Kundinnen und Kunden durch Ihre Meinung.

Kundinnen und Kunden meinen

Bewertungen (0)

Weitere Artikel finden Sie in
  • Produktbild: Digraphs
  • 1. Basic Terminology, Notation and Results. -1.1 Sets, Matrices and Vectors. -1.2 Digraphs, Subdigraphs, Neighbours, Degrees. -1.3 Isomorphism and Basic Operations on Digraphs. -1.4 Walks, Trails, Paths, Cycles and Path-Cycle Subdigraphs. -1.5 Strong and Unilateral Connectivity. -1.6 Undirected Graphs, Biorientations and Orientations. -1.7 Trees and Euler Trails in Digraphs. -1.8 Mixed Graphs, Orientations of Digraphs, and Hypergraphs. -1.9 Depth-First Search. -1.10 Exercises. -2. Classes of Digraphs. -2.1 Acyclic Digraphs. -2.2 Multipartite Digraphs and Extended Digraphs. -2.3 Transitive Digraphs, Transitive Closures and Reductions. -2.4 Line Digraphs. -2.5 The de Bruijn and Kautz Digraphs. -2.6 Series-Parallel Digraphs. -2.7 Quasi-Transitive Digraphs. -2.8 Path-Mergeable Digraphs. -2.9 Locally In/Out-Semicomplete Digraphs. -2.10 Locally Semicomplete Digraphs. -2.11 Totally F-Decomposable Digraphs. -2.12 Planar Digraphs. -2.13 Digraphs of Bounded Tree-Width -2.14 Other Families of Digraphs. -2.15 Exercises. -3. Distances. -3.1 Terminology and Notation on Distances. -3.2 Structure of Shortest Paths. -3.3 Algorithms for Finding Distances in Digraphs. -3.3.1 Breadth-First Search (BFS). -3.3.2 Acyclic Digraphs. -3.3.3 Dijkstra's Algorithm. -3.3.4 The Bellman-Ford-Moore Algorithm. -3.3.5 The Floyd-Warshall Algorithm. -3.4 Inequalities on Diameter. -3.5 Minimum Diameter of Orientations of Multigraphs. -3.6 Minimum Diameter Orientations of Some Graphs and Digraphs. -3.7 Kings in Digraphs. -3.8 (k, l)-Kernels. -3.9 Exercises. -4. Flows in Networks. -4.1 Definitions and Basic Properties. -4.2 Reductions Among Different Flow Models. -4.3 Flow Decompositions. -4.4 Working with the Residual Network. -4.5 The Maximum Flow Problem. -4.6 Polynomial Algorithms for Finding a Maximum (s, t)-Flow. -4.7 Unit Capacity Networks and Simple Networks. -4.8 Circulations and Feasible Flows. -4.9 Minimum Value Feasible (s, t)-Flows. -4.10 Minimum Cost Flows. -4.11 Applications of Flows. -4.12 Exercises. -5. Connectivity of Digraphs. -5.1 Additional Notation and Preliminaries. -5.2 Finding the Strong Components of a Digraph. -5.3 Ear Decompositions. -5.4 Menger's Theorem. -5.5 Determining Arc- and Vertex-Strong Connectivity. -5.6 Minimally k-(Arc)-Strong Directed Multigraphs. -5.7 Critically k-Strong Digraphs. -5.8 Connectivity Properties of Special Classes of Digraphs. -5.9 Disjoint X-paths in Digraphs. -5.10 Exercises. -6. Hamiltonian, Longest and Vertex-Cheapest Paths and Cycles. -6.1 Complexity. -6.2 Hamilton Paths and Cycles in Path-Mergeable Digraphs. -6.3 Hamilton Paths and Cycles in Locally In-Semicomplete Digraphs. -6.4 Hamilton Cycles and Paths in Degree-Constrained Digraphs. -6.5 Longest Paths and Cycles in Degree-Constrained Oriented Graphs. -6.6 Longest Paths and Cycles in Semicomplete Multipartite Digraphs. -6.7 Hamilton Paths and Cycles in Quasi-Transitive Digraphs. -6.8 Vertex-Cheapest Paths and Cycles. -6.9 Hamilton Paths and Cycles in Various Classes of Digraphs. -6.10 Exercises. -7. Restricted Hamiltonian Paths and Cycles. -7.1 Hamiltonian Paths with a Prescribed End-Vertex. -7.2 Weakly Hamiltonian-Connected Digraphs. -7.3 Hamiltonian-Connected Digraphs. -7.4 Hamiltonian Cycles Containing or Avoiding Prescribed Arcs. -7.5 Arc-Traceable Digraphs. -7.6 Oriented Hamiltonian Paths and Cycles. -7.7 Exercises. -8. Paths and Cycles of Prescribed Lengths. -8.1 Pancyclicity of Digraphs. -8.2 Colour Coding: Efficient Algorithms for Paths and Cycles. -8.3 Cycles of Length k Modulo p. -8.4 Girth. -8.5 Short Cycles in Semicomplete Multipartite Digraphs. -8.6 Exercises. -9. Branchings. -9.1 Tutte's Matrix Tree Theorem. -9.2 Optimum Branchings. -9.3 Arc-Disjoint Branchings. -9.4 Implications of Edmonds' Branching Theorem. -9.5 Out-Branchings with Degree Bounds. -9.6 Arc-Disjoint In- and Out-Branchings. -9.7 Out-Branchings with Extremal Number of Leaves. -9.8 The Source Location Problem. -9.9 Miscellaneous Topics. -9.10 Exercises. -10. Linkages in Digraphs. -10.1 Additional Definitions and Preliminaries. -10.2 The Complexity of the k-linkage Problem. -10.3 Sufficient Conditions for a Digraph to be k-Linked. -10.4 The k-linkage Problem for Acyclic Digraphs. -10.5 Linkages in (Generalizations of) Tournaments. -10.6 Linkages in Planar Digraphs. -10.7 Weak Linkages. -10.8 Linkages in Digraphs With Large Minimum Out-Degree. -10.9 Miscellaneous Topics. -10.10 Exercises. -11. Orientations of Graphs and Digraphs. -11.1 Underlying Graphs of Various Classes of Digraphs. -11.2 Orientations With no Even Cycles. -11.3 Colourings and Orientations of Graphs. -11.4 Orientations and Nowhere Zero Integer Flows. -11.5 Orientations Achieving High Arc-Strong Connectivity. -11.6 k-Strong Orientations. -11.7 Orientations Respecting Degree Constraints. -11.8 Submodular Flows. -11.9 Orientations of Mixed Multigraphs. -11.10 k-(Arc)-Strong Orientations of Digraphs. -11.11 Miscellaneous Topics. -11.12 Exercises. -12. Sparse Subdigraphs with Prescribed Connectivity. -12.1 Minimum Strong Spanning Subdigraphs. -12.2 Polynomially Solvable Cases of the MSSS problem. -12.3 Approximation Algorithms for the MSSS problem. -12.4 Small Certificates for k-(Arc)-Strong Connectivity. -12.5 Minimum Weight Strong Spanning Subdigraphs. 12.6 Directed Steiner Problems. -12.7 Miscellaneous Topics. -12.8 Exercises. -13. Packings, Coverings and Decompositions. 13.1 Packing Directed Cuts: The Lucchesi-Younger Theorem. -13.2 Packing Dijoins: Woodall's Conjecture. -13.3 Packing Cycles. -13.4 Arc-Disjoint Hamiltonian Paths and Cycles. -13.5 Path Factors. -13.6 Cycle Factors with the Minimum Number of Cycles. -13.7 Cycle Factors with a Fixed Number of Cycles. -13.8 Cycle Subdigraphs Covering Specified Vertices. -13.9 Proof of Gallai's Conjecture. -13.10 Decomposing a Tournament into Strong Spanning Subdigraphs. -13.11 The Directed Path-Partition Conjecture. -13.12 Miscellaneous Topics. -13.13 Exercises. -14. Increasing Connectivity. -14.1 The Splitting off Operation. -14.2 Increasing the Arc-Strong Connectivity Optimally. -14.3 Increasing the Vertex-Strong Connectivity Optimally. -14.4 Arc Reversals and Vertex-Strong Connectivity. -14.5 Arc-Reversals and Arc-Strong Connectivity. -14.6 Increasing Connectivity by Deorienting Arcs. -14.7 Miscellaneous topics. -14.8 Exercises. -15. Feedback Sets and Vertex Orderings. -15.1 Two Conjectures on Feedback Arc Sets. -15.2 Optimal Orderings in Tournaments. -15.3 Complexity of the Feedback Set Problems. -15.4 Disjoint Cycles Versus Feedback Sets. -15.5 Optimal Orderings and Seymour's Second Neighbourhood Conjecture. -15.6 Adam's Conjecture. -15.7 Exercises. -16. Generalizations of Digraphs: Edge-Coloured Multigraphs. -16.1 Terminology, Notation and Initial Observations. -16.2 Properly Coloured Euler Trails. -16.3 Properly Coloured Cycles. -16.4 Gadget Graphs and Shortest PC Cycles and (s, t)-Paths. -16.5 Long PC Cycles and Paths. -16.6 Connectivity of Edge-Coloured Multigraphs. -16.7 Alternating Cycles in 2-Edge-Coloured Bipartite Multigraphs. -16.8 Alternating Paths and Cycles in 2-Edge-Coloured Complete. -Multigraphs. -16.9 PC Paths and Cycles in c-Edge-Coloured Complete Graphs, c = 3. -16.10 Exercises. -17. Applications of Digraphs and Edge-Coloured Graphs. -17.1 A Digraph Model in Quantum Mechanics. -17.2 Embedded Computing and Convex Sets in Acyclic Digraphs. -17.3 When Greedy-Like Algorithms Fail. -17.4 Domination Analysis of ATSP Heuristics. -17.5 Solving the 2-Satisfiability Problem. -17.6 Alternating Hamilton Cycles in Genetics. -17.7 Gaussian Elimination. -17.8 Markov Chains. -17.9 List Edge-Colourings. -17.10 Digraph Models of Bartering. -17.11 PERT/CPM in Project Scheduling. -17.12 Finite Automata. -17.13 Puzzles and Digraphs. -17.14 Gossip Problems. -17.15 Deadlocks of Computer Processes. -17.16 Exercises. -18. Algorithms and their Complexity. -18.1 Combinatorial Algorithms. -18.2 NP-Complete and NP-Hard Problems. -18.3 The Satisfiability Problem. -18.4 Fixed-Parameter Tractability and Intractability. -18.5 Exponential Algorithms. -18.6 Approximation Algorithms. -18.7 Heuristics and Meta-heuristics. -18.8 Matroids. -18.9 Exercises. -References. -Symbol Index. -Author Index. -Subject Index.