Planar disjoint-paths completion

DOI10.1007/s00453-015-0046-2zbMath1350.68121DBLPjournals/algorithmica/AdlerKT16OpenAlexW2901461299WikidataQ59891863 ScholiaQ59891863MaRDI QIDQ329285

Isolde Adler, Stavros G. Kolliopoulos, Dimitrios M. Thilikos

Publication date: 21 October 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://eprints.whiterose.ac.uk/104729/1/PDPC_adler.pdf

zbMATH Keywords

planar graphscompletion problemsdisjoint paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (1)

A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Monadic second-order evaluations on tree-decomposable graphs
• Graph minors. XXI. graphs with unique linkages
• On the complexity of DNA physical mapping
• Graph minors. XIII: The disjoint paths problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A shorter proof of the graph minor algorithm
• Tight Bounds for Linkages in Planar Graphs
• Contraction Bidimensionality: The Accurate Picture
• 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

This page was built for publication: Planar disjoint-paths completion