Independent sets in extensions of 2\(K_{2}\)-free graphs
From MaRDI portal
Publication:1765375
DOI10.1016/j.dam.2004.07.006zbMath1087.90080OpenAlexW2072480005MaRDI QIDQ1765375
Raffaele Mosca, Vadim V. Lozin
Publication date: 23 February 2005
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2004.07.006
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (33)
The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs ⋮ Induced Separation Dimension ⋮ 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 ⋮ New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths ⋮ Polar graphs and maximal independent sets ⋮ Maximum weight independent sets in classes related to claw-free graphs ⋮ 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 ⋮ From matchings to independent sets ⋮ The cluster deletion problem for cographs ⋮ Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time ⋮ Unnamed Item ⋮ Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs ⋮ Independent sets in graphs ⋮ Critical hereditary graph classes: a survey ⋮ A polynomial algorithm to find an independent set of maximum weight in a fork-free graph ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ On Toughness and Hamiltonicity of 2K2‐Free Graphs ⋮ Independent domination in finitely defined classes of graphs: polynomial algorithms ⋮ Maximum independent sets in subclasses of \(P_{5}\)-free graphs ⋮ Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs ⋮ The Maximum Independent Set Problem in Planar Graphs ⋮ On the complexity of the independent set problem in triangle graphs ⋮ Upper domination: towards a dichotomy through boundary properties ⋮ The induced separation dimension of a graph ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ Sparse regular induced subgraphs in \(2P_3\)-free graphs ⋮ On the inapproximability of independent domination in \(2P_3\)-free perfect graphs ⋮ Independent domination versus weighted independent domination ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
- Finding augmenting chains in extensions of claw-free graphs
- On domination problems for permutation and other graphs
- On diameters and radii of bridged graphs
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Independent domination in chordal graphs
- On the stability number of claw-free \(P_5\)-free and more general graphs
- A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
- On semi-\(P_ 4\)-sparse graphs
- Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
- On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
- Independent domination in finitely defined classes of graphs
- On variations of \(P_{4}\)-sparse graphs
- An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- \(P_{5}\)-free augmenting graphs and the maximum stable set problem
- Some results on maximum stable sets in certain \(P_{5}\)-free graphs
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- Stability in \(P_5\)- and banner-free graphs
- On \(\alpha\)-redundant vertices in \(P_{5}\)-free graphs
- On (\(P_{5}\), diamond)-free graphs
- On the stable set problem in special \(P_{5}\)-free graphs
- On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
- Augmenting chains in graphs without a skew star.
- A New Algorithm for Generating All the Maximal Independent Sets
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- An upper bound on the number of cliques in a graph
- A note on \(\alpha\)-redundant vertices in graphs
This page was built for publication: Independent sets in extensions of 2\(K_{2}\)-free graphs
