Mim-width. I. Induced path problems

DOI10.1016/j.dam.2019.06.026zbMath1437.05223OpenAlexW2962055031WikidataQ127465558 ScholiaQ127465558MaRDI QIDQ2174563

Jan Arne Telle, Lars Jaffke, O-joung Kwon

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

zbMATH Keywords

Hamiltonian cyclegraph classesinduced pathsgraph width parametersinduced topological minors

Mathematics Subject Classification ID

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

Related Items (16)

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 ⋮ 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 ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ 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 ⋮ Mim-width. II. The feedback vertex set problem ⋮ Induced disjoint paths in AT-free graphs ⋮ Distance Domination in Graphs ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Few induced disjoint paths for \(H\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Graph classes with structured neighborhoods and algorithmic applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• Finding Hamiltonian circuits in interval graphs
• Algorithms for maximum weight induced paths
• A width parameter useful for chordal and co-comparability graphs
• Graph minors. XIII: The disjoint paths problem
• HAMILTONian circuits in chordal bipartite graphs
• Induced disjoint paths in AT-free graphs
• Detecting fixed patterns in chordal graphs in polynomial time
• Mim-width. II. The feedback vertex set problem
• Mim-width. III. Graph powers and generalized distance domination problems
• The \(k\)-in-a-path problem for claw-free graphs
• Induced disjoint paths in circular-arc graphs in linear time
• The point-set embeddability problem for plane graphs
• The Induced Disjoint Paths Problem
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Hamilton Paths in Grid Graphs
• Parameterized Algorithms
• Hardness of computing width parameters based on branch decompositions over the vertex set
• Graph-Theoretic Concepts in Computer Science

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