On easy and hard hereditary classes of graphs with respect to the independent set problem
From MaRDI portal
Publication:1414579
DOI10.1016/S0166-218X(03)00387-1zbMath1029.05140MaRDI QIDQ1414579
Publication date: 4 December 2003
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (53)
Boundary classes of graphs for the dominating set problem ⋮ Tree-width dichotomy ⋮ The width and integer optimization on simplices with bounded minors of the constraint matrices ⋮ Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs ⋮ A complexity dichotomy and a new boundary class for the dominating set problem ⋮ Structure of squares and efficient domination in graph classes ⋮ Vertex coloring of graphs with few obstructions ⋮ A sufficient condition to extend polynomial results for the maximum independent set problem ⋮ New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Boundary classes for graph problems involving non-local properties ⋮ From matchings to independent sets ⋮ Boundary properties of well-quasi-ordered sets of graphs ⋮ Contraction Blockers for Graphs with Forbidden Induced Paths ⋮ On the number of boundary classes in the 3-colouring problem ⋮ Clique‐width: Harnessing the power of atoms ⋮ Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Critical properties of bipartite permutation graphs ⋮ Boundary Classes of Planar Graphs ⋮ Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ \textsc{max-cut} and containment relations in graphs ⋮ Unnamed Item ⋮ Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs ⋮ On König graphs with respect to P4 ⋮ Boundary graph classes for some maximum induced subgraph problems ⋮ The coloring problem for classes with two small obstructions ⋮ Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs ⋮ NP-hard graph problems and boundary classes of graphs ⋮ On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem ⋮ A new graph construction of unbounded clique-width ⋮ Critical hereditary graph classes: a survey ⋮ Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ Boundary properties of graphs for algorithmic graph problems ⋮ Augmenting chains in graphs without a skew star. ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ max-cut and Containment Relations in Graphs ⋮ Upper domination: towards a dichotomy through boundary properties ⋮ A boundary class for the \(k\)-path partition problem ⋮ Role colouring graphs in hereditary classes ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ A Boundary Property for Upper Domination ⋮ Boundary Properties of Factorial Classes of Graphs ⋮ Some results on graphs without long induced paths ⋮ Hereditary classes of graphs: a parametric approach ⋮ Critical elements in combinatorially closed families of graph classes ⋮ The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs ⋮ A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
- Decomposition by clique separators
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- On (\(P_{5}\), diamond)-free graphs
- On the stable set problem in special \(P_{5}\)-free graphs
- On graphs with polynomially solvable maximum-weight clique problem
- A New Algorithm for Generating All the Maximal Independent Sets
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- A note on \(\alpha\)-redundant vertices in graphs
This page was built for publication: On easy and hard hereditary classes of graphs with respect to the independent set problem
