FPT algorithms to recognize well covered graphs

MaRDI QIDQ5377222zbMATH OpenFDO

Authors Rafael T. Araújo, Eurinardo R. Costa, Sulamita Klein, Uéverton S. Souza, Rudini M. Sampaio

Publication date 23 May 2019

Full work available at URL https://arxiv.org/abs/1810.08276, https://dmtcs.episciences.org/5342/pdf

zbMATH Keywords

degenerate graphsfixed parameter tractabilitypolynomial kernelprimeval decompositionwell covered graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Recognizing well covered graphs of families with special \(P _{4}\)-components
• Complexity results for well‐covered graphs
• The structure of well-covered graphs and the complexity of their recognition problems
• scientific article; zbMATH DE number 205349
• A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles

Cited in

(5)

• Partitions and well-coveredness: the graph sandwich problem
• On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity
• On the probe problem for (r, )-well-coveredness
• Recognizing well-dominated graphs is coNP-complete
• Computing well-covered vector spaces of graphs using modular decomposition

This page was built for publication: FPT algorithms to recognize well covered graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5377222)