Graph minors. XIII: The disjoint paths problem
From MaRDI portal
Publication:1892832
DOI10.1006/jctb.1995.1006zbMath0823.05038WikidataQ55881137 ScholiaQ55881137MaRDI QIDQ1892832
Publication date: 2 July 1995
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jctb.1995.1006
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C38: Paths and cycles
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Graphs with the Circuit Cover Property, Unnamed Item, Linkless embeddings of graphs in 3-space, Unnamed Item, Mineurs d'arbres avec racines, A simple linear-time algorithm for finding path-decompositions of small width, Fixed-parameter tractability and completeness II: On completeness for W[1], Mixed searching and proper-path-width, Advice classes of parametrized tractability, Primal-dual approximation algorithms for integral flow and multicut in trees, Self-witnessing polynomial-time complexity and prime factorization, On the complexity of finding iso- and other morphisms for partial \(k\)- trees, Complexity of path-forming games, All structured programs have small tree width and good register allocation, Upper bounds on the size of obstructions and intertwines, A partial k-arboretum of graphs with bounded treewidth, On the complexity of database queries, Embeddings of graphs, Improved self-reduction algorithms for graphs with bounded treewidth, Obstruction set isolation for the gate matrix layout problem, On search, decision, and the efficiency of polynomial-time algorithms, Rooted routing in the plane, On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory, On interval routing schemes and treewidth, Removable circuits in multigraphs, Algorithms and obstructions for linear-width and related search parameters, Alternating paths in edge-colored complete graphs, Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues], Highly linked graphs, Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs, Polynomial-time self-reducibility: theoretical motivations and practical results∗, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues, Finding disjoint paths with different path-costs: Complexity and algorithms, Optimal Construction of Edge-Disjoint Paths in Random Graphs
