On the probe problem for (r, )-well-coveredness: algorithms and complexity

DOI10.1016/J.TCS.2022.08.006MaRDI QIDQ2172604zbMATH OpenOpenAlexFDO

Authors Uéverton S. Souza, Luerbio Faria

Publication date 16 September 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2022.08.006

zbMATH Keywords

\((r,\ell)\)-graphcomplexityproberecognition

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On the (parameterized) complexity of recognizing well-covered (r,)-graphs
• On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
• Graph sandwich problem for the property of being well-covered and partitionable into \(k\) independent sets and \(\ell\) cliques

Cites work

• A characterization of chain probe graphs
• A characterization of well covered graphs of girth 5 or greater
• A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
• Chordal probe graphs
• Complexity results for well‐covered graphs
• Computing and Combinatorics
• FPT algorithms to recognize well covered graphs
• Graph sandwich problem for the property of being well-covered and partitionable into \(k\) independent sets and \(\ell\) cliques
• Graph Sandwich Problems
• scientific article; zbMATH DE number 434906 (Why is no real title available?)
• scientific article; zbMATH DE number 4202288 (Why is no real title available?)
• scientific article; zbMATH DE number 3614795 (Why is no real title available?)
• scientific article; zbMATH DE number 205349 (Why is no real title available?)
• List matrix partitions of chordal graphs
• List Partitions
• On probe interval graphs
• On probe permutation graphs
• On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
• Partitioning cographs into cliques and stable sets
• Partitions of graphs into one or two independent sets and cliques
• Probe Ptolemaic Graphs
• Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs
• Recognizing well covered graphs of families with special \(P _{4}\)-components
• Some covering concepts in graphs
• The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
• The strong perfect graph theorem
• Two characterizations of chain partitioned probe graphs
• Well covered simplicial, chordal, and circular arc graphs
• Well-covered claw-free graphs

Cited in

(5)

• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• Partitions and well-coveredness: the graph sandwich problem
• scientific article; zbMATH DE number 6474898 (Why is no real title available?)
• Recognizing well-dominated graphs is coNP-complete
• On conflict-free spanning tree: mapping tractable and hard instances through the lenses of graph classes

This page was built for publication: On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity

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