Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width

DOI10.4230/LIPICS.IPEC.2017.21MaRDI QIDQ5111880zbMATH OpenFDO

Authors Lars Jaffke, O-joung Kwon, Jan Arne Telle

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1708.04536

zbMATH Keywords

dynamic programminggraph classesinduced pathsgraph width parametersinduced topological minors

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Mim-width. I. Induced path problems
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
• Bounding the mim‐width of hereditary graph classes
• Mim-width. II. The feedback vertex set problem

Cites work

• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Algorithms for maximum weight induced paths
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Graph classes with structured neighborhoods and algorithmic applications
• Graph minors. XIII: The disjoint paths problem
• Graph-Theoretic Concepts in Computer Science
• Hardness of computing width parameters based on branch decompositions over the vertex set
• Induced disjoint paths in circular-arc graphs in linear time
• Mim-width. III. Graph powers and generalized distance domination problems
• The Induced Disjoint Paths Problem
• The \(k\)-in-a-path problem for claw-free graphs
• The point-set embeddability problem for plane graphs

Cited in

(10)

• Mim-width. III. Graph powers and generalized distance domination problems
• Mim-width. II. The feedback vertex set problem
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• scientific article; zbMATH DE number 7378700 (Why is no real title available?)
• On the tractability of optimization problems on \(H\)-graphs
• Algorithms for maximum weight induced paths
• On exact solution approaches for the longest induced path problem
• Mim-width. I. Induced path problems
• More applications of the \(d\)-neighbor equivalence: connectivity and acyclicity constraints
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width

This page was built for publication: Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width

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