Disjoint paths in graphs

DOI10.1016/0012-365X(80)90158-2zbMath0457.05043OpenAlexW4210246355MaRDI QIDQ1150632

Publication date: 1980

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(80)90158-2

zbMATH Keywords

edge-disjoint paths

Mathematics Subject Classification ID

Paths and cycles (05C38)

Related Items

The structure of graphs with no K3,3 immersion, 4‐Separations in Hajós graphs, A graph minor condition for graphs to be \(k\)-linked, Homomorphisms of Cayley graphs and cycle double covers, On a coloring conjecture of Hajós, Walking through waypoints, Shortest Two Disjoint Paths in Polynomial Time, Connectivity for Kite-Linked Graphs, Unnamed Item, Unnamed Item, Edge-disjoint odd cycles in 4-edge-connected graphs, Linkage for the diamond and the path with four vertices, Adjacency in binary matroids, Rooted routing in the plane, The complexity of induced minors and related problems, Finding Two Edge-Disjoint Paths with Length Constraints, Paths and edge-connectivity in graphs. III: Six-terminal k paths, Obstructions for two-vertex alternating embeddings of graphs in surfaces, Non-planar extensions of subdivisions of planar graphs, The structure of graphs not topologically containing the Wagner graph, Subdivisions in apex graphs, Characterization of \((m, n)\)-linked planar graphs, Tutte's edge-colouring conjecture, Three commodity flows in graphs, Finding a path with two labels forbidden in group-labeled graphs, Independent paths and \(K_{5}\)-subdivisions, On orientations and shortest paths, Some recent progress and applications in graph minor theory, When Do Gomory--Hu Subtrees Exist?, The reduction of graph families closed under contraction, Linking four vertices in graphs of large connectivity, Projective plan and Möbius band obstructions, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, Obstructions for the Disk and the Cylinder Embedding Extension Problems, Rooted \(K_4\)-minors, The disjoint shortest paths problem, Multiple weak 2-linkage and its applications on integer flows of signed graphs, The Induced Disjoint Paths Problem, The disjoint paths problem in quadratic time, Bonds with parity constraints, Linkless and flat embeddings in 3-space, Optimal connectivity for fat-triangle linkages, 2-linked graphs, On shortest disjoint paths in planar graphs, Graph theory. Abstracts from the workshop held January 2--8, 2022, Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem, Packing cycles through prescribed vertices under modularity constraints, The 1-fixed-endpoint path cover problem is Polynomial on interval graphs, Criticality for multicommodity flows, Optimal parallel algorithms for path problems on planar graphs, The extremal function for 3-linked graphs, Biased graphs with no two vertex-disjoint unbalanced cycles, The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs, A new proof of the flat wall theorem, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, On obstructions to small face covers in planar graphs, On finite convexity spaces induced by sets of paths in graphs, Links in edge-colored graphs, General vertex disjoint paths in series-parallel graphs, Induced disjoint paths problem in a planar digraph, A linear algorithm for the all-bidirectional-edges problem on planar graphs, Half-integral packing of odd cycles through prescribed vertices, An improved linear edge bound for graph linkages, The extremal function for \(K_{9}\) minors, 4-connected triangulations and 4-orderedness, A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs, Improved Algorithms for the 2-Vertex Disjoint Paths Problem, Unnamed Item, Shortest \((A+B)\)-path packing via hafnian, Cycle double covers of infinite planar graphs, 7-connected graphs are 4-ordered, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, Graph minor theory, Removable cycles in non-bipartite graphs, Two disjoint shortest paths problem with non-negative edge length, A simpler proof for the two disjoint odd cycles theorem, The linkedness of cubical polytopes: the cube, On linkages in polytope graphs, Inseparability graphs of oriented matroids, K₅-Subdivisions in Graphs, Graph minors. IX: Disjoint crossed paths, Bounds on path connectivity, Variational analysis down under open problem session, Structure and recognition of graphs with no 6-wheel subdivision, Arc-Disjoint Directed and Undirected Cycles in Digraphs, Graphs with at most one crossing, The Kelmans-Seymour conjecture. I: Special separations, The Kelmans-Seymour conjecture. II: 2-vertices in \(K_4^-\), The Kelmans-Seymour conjecture. III: 3-vertices in \(K_4^-\), The Kelmans-Seymour conjecture. IV: A proof, Highly linked graphs, Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs, The Directed Disjoint Shortest Paths Problem, Cliques, minors and apex graphs, Frustration-critical signed graphs, Two edge-disjoint paths with length constraints, Disjoint sub(di)graphs in digraphs, On the definability of properties of finite graphs, The extremal function for \(K_{8}^{-}\) minors, Surfaces, tree-width, clique-minors, and partitions, The 2-linkage problem for acyclic digraphs, Electrical flows over spanning trees, Rooted topological minors on four vertices, Paths and edge-connectivity in graphs, Disjoint Paths—A Survey, Hadwiger's conjecture for \(K_ 6\)-free graphs, Fixed-parameter tractability for subset feedback set problems with parity constraints, An approach to the subgraph homeomorphism problem, Subdivisions of \(K_5\) in graphs containing \(K_{2,3}\), Edge-disjoint paths in planar graphs

Cites Work