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

graph classesgraph width parametersHamiltonian cycleinduced pathsinduced topological minors

Mathematics Subject Classification ID

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

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 maximum weight induced paths
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• 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
• Hamilton Paths in Grid Graphs
• HAMILTONian circuits in chordal bipartite 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 \(k\)-in-a-path problem for claw-free graphs
• The Induced Disjoint Paths Problem
• The point-set embeddability problem for plane graphs

Cited in

(32)

• Algorithms for maximum weight induced paths
• Few induced disjoint paths for \(H\)-free graphs
• List k-colouring P_t-free graphs: a mim-width perspective
• Mim-width. II. The feedback vertex set problem
• Lower bounds on the mim-width of some graph classes
• New formulations and branch-and-cut procedures for the longest induced path problem
• On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
• Distance domination in graphs
• More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
• Generalized distance domination problems and their complexity on graphs of bounded mim-width
• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• Induced disjoint paths and connected subgraphs for H-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Fair allocation algorithms for indivisible items under structured conflict constraints
• Bounding the mim‐width of hereditary graph classes
• MIP formulations for induced graph optimization problems: a tutorial
• Contracting to a longest path in H-free graphs
• Bounding the Mim-Width of Hereditary Graph Classes.
• Few induced disjoint paths for \(H\)-free graphs
• Classes of intersection digraphs with good algorithmic properties
• New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Isometric path complexity of graphs
• Finding induced subgraphs from graphs with small mim-width
• The simultaneous interval number: a new width parameter that measures the similarity to interval graphs
• A survey of degree-boundedness
• On the hardness of generalized domination problems parameterized by mim-width
• Comparing width parameters on graph classes
• Complexity framework for forbidden subgraphs. I: The framework
• Hamiltonicity parameterized by mim-width is (indeed) para-NP-hard
• Improved algorithms for perfect graphs and odd holes

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)