Mim-width. I. Induced path problems

DOI10.1016/J.DAM.2019.06.026MaRDI QIDQ2174563zbMATH OpenOpenAlexWikidataFDO

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

Publication date 21 April 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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

Cites work

• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
• 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
• Detecting fixed patterns in chordal graphs in polynomial time
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Finding Hamiltonian circuits in interval graphs
• Fundamentals of parameterized complexity
• Graph classes with structured neighborhoods and algorithmic applications
• Graph minors. XIII: The disjoint paths problem
• Graph theory
• Graph-Theoretic Concepts in Computer Science
• HAMILTONian circuits in chordal bipartite graphs
• Hamilton Paths in Grid Graphs
• 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. II. The feedback vertex set problem
• Mim-width. III. Graph powers and generalized distance domination problems
• Parameterized algorithms
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• 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

(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
• New formulations and branch-and-cut procedures for the longest induced path problem
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• 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)