Mim-width. I. Induced path problems

DOI10.1016/J.DAM.2019.06.026zbMATH Open1437.05223OpenAlexW2962055031WikidataQ127465558 ScholiaQ127465558MaRDI QIDQ2174563FDOQ2174563

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

Publication date: 21 April 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2019.06.026

Recommendations

• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• Bounding the mim‐width of hereditary graph classes
• Mim-width. II. The feedback vertex set problem
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width

zbMATH Keywords

Hamiltonian cyclegraph classesinduced pathsgraph width parametersinduced topological minors

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Cites Work

• Graph theory
• Fundamentals of parameterized complexity
• Graph minors. XIII: The disjoint paths problem
• Hamilton Paths in Grid Graphs
• Parameterized algorithms
• HAMILTONian circuits in chordal bipartite graphs
• 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
• Finding Hamiltonian circuits in interval graphs
• Detecting fixed patterns in chordal graphs in polynomial time
• The Induced Disjoint Paths Problem
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Mim-width. II. The feedback vertex set problem
• Hardness of computing width parameters based on branch decompositions over the vertex set
• The \(k\)-in-a-path problem for claw-free graphs
• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• The point-set embeddability problem for plane graphs
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
• Induced disjoint paths in circular-arc graphs in linear time
• Mim-width. III. Graph powers and generalized distance domination problems

Cited In (23)

• Few induced disjoint paths for \(H\)-free graphs
• Few induced disjoint paths for \(H\)-free graphs
• Generalized distance domination problems and their complexity on graphs of bounded mim-width
• Bounding the Mim-Width of Hereditary Graph Classes.
• On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs
• More applications of the \(d\)-neighbor equivalence: acyclicity and connectivity constraints
• List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective
• Mim-width. II. The feedback vertex set problem
• MIP formulations for induced graph optimization problems: a tutorial
• Fair allocation algorithms for indivisible items under structured conflict constraints
• Algorithms for maximum weight induced paths
• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• Classes of intersection digraphs with good algorithmic properties
• Contracting to a longest path in H-free graphs
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Distance domination in graphs
• New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• New formulations and branch-and-cut procedures for the longest induced path problem
• Bounding the mim‐width of hereditary graph classes
• Lower bounds on the mim-width of some graph classes
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width

This page was built for publication: Mim-width. I. Induced path problems

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