Finding an induced path of given parity in planar graphs in polynomial time

MaRDI QIDQ5743428zbMATH OpenFDO

Authors Marcin Kamiński, N. Nishimura

Publication date 10 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=2095171

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Finding induced paths of given parity in claw-free graphs
• Finding induced paths of given parity in claw-free graphs
• The complexity of induced minors and related problems
• Induced disjoint paths problem in a planar digraph
• Algorithms for finding an induced cycle in planar graphs

Cites work

• A linear algorithm for the group path problem on chordal graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A new property of critical imperfect graphs and some consequences
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
• Efficient reduction for path problems on circular-arc graphs
• Finding an Even Simple Path in a Directed Planar Graph
• Finding induced paths of given parity in claw-free graphs
• Graphs on surfaces
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Modularity of cycles and paths in graphs
• On the complexity of finding even pairs in planar perfect graphs
• On the complexity of testing for odd holes and induced odd paths
• Path parity and perfection
• Quickly excluding a planar graph
• Recognizing Perfect 2-Split Graphs
• Recognizing planar strict quasi-parity graphs
• The even-path problem for graphs and digraphs
• The Graph Minor Algorithm with Parity Conditions
• The Induced Disjoint Paths Problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The parity path problem on some subclasses of perfect graphs
• The Strong Perfect Graph Conjecture for Planar Graphs
• Transformations which Preserve Perfectness and H-Perfectness of Graphs

Cited in

(16)

• The complexity of induced minors and related problems
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• The parity path problem on some subclasses of perfect graphs
• Finding induced paths of given parity in claw-free graphs
• On the complexity of finding even pairs in planar perfect graphs
• scientific article; zbMATH DE number 475588 (Why is no real title available?)
• Finding an Even Simple Path in a Directed Planar Graph
• Finding induced paths of given parity in claw-free graphs
• Finding a shortest even hole in polynomial time
• Combing a Linkage in an Annulus
• scientific article; zbMATH DE number 7765379 (Why is no real title available?)
• Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center
• Algorithms for finding an induced cycle in planar graphs
• A more accurate view of the flat wall theorem
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Improved algorithms for perfect graphs and odd holes

This page was built for publication: Finding an induced path of given parity in planar graphs in polynomial time

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