On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity
From MaRDI portal
Publication:2172604
DOI10.1016/j.tcs.2022.08.006OpenAlexW4292381379MaRDI QIDQ2172604
Uéverton S. Souza, Luérbio 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
Related Items (2)
Recognizing well-dominated graphs is coNP-complete ⋮ Partitions and well-coveredness: the graph sandwich problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A characterization of chain probe graphs
- Two characterizations of chain partitioned probe graphs
- List matrix partitions of chordal graphs
- The strong perfect graph theorem
- The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
- On probe permutation graphs
- A characterization of well covered graphs of girth 5 or greater
- On probe interval graphs
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- Chordal probe graphs
- Partitions of graphs into one or two independent sets and cliques
- Well-covered claw-free graphs
- Graph sandwich problem for the property of being well-covered and partitionable into \(k\) independent sets and \(\ell\) cliques
- Recognizing well covered graphs of families with special \(P _{4}\)-components
- Partitioning cographs into cliques and stable sets
- Probe Ptolemaic Graphs
- Complexity results for well‐covered graphs
- A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
- List Partitions
- Graph Sandwich Problems
- Well covered simplicial, chordal, and circular arc graphs
- Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs
- Some covering concepts in graphs
- Computing and Combinatorics
This page was built for publication: On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity
