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

DOI10.4230/LIPICS.IPEC.2017.21zbMATH Open1443.68131arXiv1708.04536MaRDI QIDQ5111880FDOQ5111880

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

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

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)

Cites Work

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

Cited In (10)

• Mim-width. III. Graph powers and generalized distance domination problems
• Mim-width. II. The feedback vertex set problem
• Title not available (Why is that?)
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• 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)