Planar disjoint-paths completion

DOI10.1007/S00453-015-0046-2MaRDI QIDQ329285zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

Recommendations

• Planar disjoint-paths completion
• FPT algorithms for plane completion problems
• On shortest disjoint paths in planar graphs
• On shortest disjoint paths in planar graphs
• Variants of plane diameter completion

Cites work

• scientific article; zbMATH DE number 5485472 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 475595 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A shorter proof of the graph minor algorithm: the unique linkage theorem
• Computing the Minimum Fill-In is NP-Complete
• Contraction Bidimensionality: The Accurate Picture
• Finding topological subgraphs is fixed-parameter tractable
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XXI. graphs with unique linkages
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Monadic second-order evaluations on tree-decomposable graphs
• On the complexity of DNA physical mapping
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Tight bounds for linkages in planar graphs
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs

Cited in

(5)

• Planar disjoint-paths completion
• Variants of plane diameter completion
• Removing Connected Obstacles in the Plane is FPT
• A survey of parameterized algorithms and the complexity of edge modification
• FPT algorithms for plane completion problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q329285)