Complexity results for well‐covered graphs
From MaRDI portal
Publication:3993632
DOI10.1002/net.3230220304zbMath0780.90104OpenAlexW2166890675MaRDI QIDQ3993632
Ramesh S. Sankaranarayana, Lorna K. Stewart
Publication date: 23 July 1992
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230220304
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Satgraphs and independent domination. I ⋮ Recognizing well covered graphs of families with special \(P _{4}\)-components ⋮ The structure of well-covered graphs and the complexity of their recognition problems ⋮ Well-covered triangulations. IV ⋮ Recursively decomposable well-covered graphs ⋮ The structure of well-covered graphs with no cycles of length 4 ⋮ WELL-COVERED GRAPHS: A SURVEY ⋮ Graphs with maximal induced matchings of the same size ⋮ Well-dominated graphs without cycles of lengths 4 and 5 ⋮ Well-hued graphs ⋮ 1-extendability of independent sets ⋮ On 4-connected claw-free well-covered graphs ⋮ On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity ⋮ A characterization of Zm-well-covered graphs of girth 6 or more ⋮ Edge-stable equimatchable graphs ⋮ Extending Berge's and Favaron's results about well-covered graphs ⋮ On CIS circulants ⋮ A classification of 1-well-covered graphs ⋮ Recognizing well-dominated graphs is coNP-complete ⋮ On maximum ratio clique relaxations ⋮ Recognizing generating subgraphs in graphs without cycles of lengths 6 and 7 ⋮ On the structure of 4-regular planar well-covered graphs ⋮ On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs ⋮ Well-covered circulant graphs ⋮ Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\) ⋮ Computing well-covered vector spaces of graphs using modular decomposition ⋮ Well-covered graphs with constraints on \(\Delta\) and \(\delta\) ⋮ Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs ⋮ On the probe problem for \((r,\ell )\)-well-coveredness ⋮ On well-covered triangulations. I ⋮ Graphs vertex-partitionable into strong cliques ⋮ On relating edges in graphs without cycles of length 4 ⋮ ModelingK-coteries by well-covered graphs ⋮ Weighted well-covered claw-free graphs ⋮ Triangulations and equality in the domination chain ⋮ On well-covered pentagonalizations of the plane ⋮ On well-covered triangulations. II. ⋮ On well-covered triangulations. III ⋮ Well-covered graphs and factors ⋮ 1-extendability of independent sets ⋮ On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph ⋮ Complexity results for generating subgraphs ⋮ On the well-coveredness of Cartesian products of graphs ⋮ Strong cliques in diamond-free graphs ⋮ VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS ⋮ Weighted well-covered graphs without cycles of lengths 5, 6 and 7 ⋮ Greedily constructing maximal partial \(f\)-factors ⋮ Detecting strong cliques ⋮ Mind the independence gap ⋮ Unnamed Item ⋮ A characterization of well-covered graphs in terms of forbidden costable subgraphs ⋮ The Clique Corona Operation and Greedoids ⋮ Recognizing Generating Subgraphs Revisited ⋮ Well-covered graphs without cycles of lengths 4, 5 and 6 ⋮ Well-covered graphs and extendability ⋮ Partitions and well-coveredness: the graph sandwich problem ⋮ The maximum ratio clique problem
Cites Work
