Independent sets in extensions of 2K₂-free graphs
From MaRDI portal
Publication:1765375
DOI10.1016/J.DAM.2004.07.006zbMATH Open1087.90080OpenAlexW2072480005MaRDI QIDQ1765375FDOQ1765375
Authors: Raffaele Mosca, Vadim 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
Recommendations
- New results on independent sets in extensions of \(2K_2\)-free graphs
- A sufficient condition to extend polynomial results for the maximum independent set problem
- Independent sets in some classes of \(S_{i,j,k}\)-free graphs
- Maximum weight independent sets in classes related to claw-free graphs
- The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
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)
Cites Work
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Title not available (Why is that?)
- A New Algorithm for Generating All the Maximal Independent Sets
- On maximal independent sets of vertices in claw-free graphs
- On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
- On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
- On domination problems for permutation and other graphs
- Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
- On diameters and radii of bridged graphs
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- Finding augmenting chains in extensions of claw-free graphs
- An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
- \(P_{5}\)-free augmenting graphs and the maximum stable set problem
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- A note on \(\alpha\)-redundant vertices in graphs
- Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- Title not available (Why is that?)
- Independent domination in chordal graphs
- On variations of \(P_{4}\)-sparse graphs
- On the stable set problem in special \(P_{5}\)-free graphs
- Independent domination in finitely defined classes of graphs
- A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
- Some results on maximum stable sets in certain \(P_{5}\)-free graphs
- An upper bound on the number of cliques in a graph
- On the stability number of claw-free \(P_5\)-free and more general graphs
- On semi-\(P_ 4\)-sparse graphs
- Stability in \(P_5\)- and banner-free graphs
- On \(\alpha\)-redundant vertices in \(P_{5}\)-free graphs
- On (\(P_{5}\), diamond)-free graphs
- Augmenting chains in graphs without a skew star.
Cited In (36)
- The cluster deletion problem for cographs
- Counting edge-injective homomorphisms and matchings on restricted graph classes
- Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs
- A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
- Independent sets in some classes of \(S_{i,j,k}\)-free graphs
- The Maximum Independent Set Problem in Planar Graphs
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- The maximum weight stable set problem in (\(P_6\), bull)-free graphs
- New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths
- On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
- Title not available (Why is that?)
- Polar graphs and maximal independent sets
- The induced separation dimension of a graph
- Upper domination: towards a dichotomy through boundary properties
- Maximum weight independent sets in classes related to claw-free graphs
- New results on independent sets in extensions of \(2K_2\)-free graphs
- From matchings to independent sets
- Sparse regular induced subgraphs in \(2P_3\)-free graphs
- Independent domination versus weighted independent domination
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- Independent sets in graphs
- A generalization of an independent set with application to \((K_q; k)\)-stable graphs
- Critical hereditary graph classes: a survey
- Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs
- Independent domination in finitely defined classes of graphs: polynomial algorithms
- Tent and a subclass of \(P_{5}\)-free graphs
- A complexity dichotomy and a new boundary class for the dominating set problem
- On the complexity of the independent set problem in triangle graphs
- Independent sets in \((P_4+P_4\),triangle)-free graphs
- A sufficient condition to extend polynomial results for the maximum independent set problem
- Maximum independent sets in subclasses of \(P_{5}\)-free graphs
- Induced separation dimension
- Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
- Independent Sets in Classes Related to Chair-Free Graphs
- On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
- Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
This page was built for publication: Independent sets in extensions of 2\(K_{2}\)-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1765375)
