Some results on graphs without long induced paths

DOI10.1016/j.ipl.2003.07.004zbMath1178.68285OpenAlexW1990092116MaRDI QIDQ1029004

Publication date: 9 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2003.07.004

zbMATH Keywords

algorithms computational complexity independent set graph algorithms forbidden induced subgraph

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (47)

Augmenting approach for some maximum set problems ⋮ Lower and upper bounds for long induced paths in 3-connected planar graphs ⋮ Weighted independent sets in classes of \(P_6\)-free graphs ⋮ Combinatorics and algorithms for augmenting graphs ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ 4-colorability of \(P_6\)-free graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths ⋮ Graphs with maximal induced matchings of the same size ⋮ Unnamed Item ⋮ A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs ⋮ New formulations and branch-and-cut procedures for the longest induced path problem ⋮ On the parameterized complexity of the acyclic matching problem ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ An improved approximation algorithm for the minimum 3-path partition problem ⋮ Tree-Width and Optimization in Bounded Degree Graphs ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs ⋮ Unnamed Item ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ On computing the minimum 3-path vertex cover and dissociation number of graphs ⋮ On the vertex \(k\)-path cover ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs ⋮ On the complexity of 4-coloring graphs without long induced paths ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ On sequential heuristic methods for the maximum independent set problem ⋮ On the approximability of the maximum induced matching problem ⋮ Kernels for packing and covering problems ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ On the complexity of the independent set problem in triangle graphs ⋮ The complexity of dissociation set problems in graphs ⋮ On a relation between \(k\)-path partition and \(k\)-path vertex cover ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ New kernels for several problems on planar graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ The parameterized complexity of the induced matching problem ⋮ Mind the independence gap ⋮ Extending the MAX algorithm for maximum independent set ⋮ New sufficient conditions for \(\alpha\)-redundant vertices ⋮ Squares of Intersection Graphs and Induced Matchings ⋮ The \(k\)-separator problem: polyhedra, complexity and approximation results

Cites Work

This page was built for publication: Some results on graphs without long induced paths