Planar Disjoint-Paths Completion
From MaRDI portal
Publication:2891339
DOI10.1007/978-3-642-28050-4_7zbMath1352.68090arXiv1511.04952MaRDI QIDQ2891339
Isolde Adler, Dimitrios M. Thilikos, Stavros G. Kolliopoulos
Publication date: 15 June 2012
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1511.04952
68Q25: Analysis of algorithms and problem complexity
05C38: Paths and cycles
05C10: Planar graphs; geometric and topological aspects of graph theory
Related Items
Unnamed Item, Irrelevant vertices for the planar disjoint paths problem, A polynomial-time algorithm for outerplanar diameter improvement, Tight Bounds for Linkages in Planar Graphs, A Polynomial-Time Algorithm for Outerplanar Diameter Improvement
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of DNA physical mapping
- Graph minors. XIII: The disjoint paths problem
- A shorter proof of the graph minor algorithm
- Tight Bounds for Linkages in Planar Graphs
- Computing the Minimum Fill-In is NP-Complete
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Finding topological subgraphs is fixed-parameter tractable