On the (parameterized) complexity of recognizing well-covered (r,)-graph
DOI10.1016/J.TCS.2018.06.024zbMATH Open1400.68078OpenAlexW2995257617MaRDI QIDQ1784741FDOQ1784741
Authors: Sancrey Rodrigues Alves, Konrad Dabrowski, Sulamita Klein, Ignasi Sau, Uéverton S. Souza, Luerbio Faria 
Publication date: 27 September 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2018.06.024
Recommendations
- On the (parameterized) complexity of recognizing well-covered \((r,\ell)\)-graphs
- Partitions and well-coveredness: the graph sandwich problem
- Parameterized algorithms on perfect graphs for deletion to \((r,\ell)\)-graphs
- Complexity results for well‐covered graphs
- The structure of well-covered graphs with no cycles of length 4
parameterized complexitywell-covered graphcoNP-completenessFPT-algorithm\((r, \ell)\)-graphcoW[2-hardness]
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Fundamentals of parameterized complexity
- Reducibility among combinatorial problems
- Graph minors. X: Obstructions to tree-decomposition
- Paths, Trees, and Flowers
- Some covering concepts in graphs
- Algorithmic meta-theorems for restrictions of treewidth
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Graph structure and monadic second-order logic. A language-theoretic approach
- On the clique-width of some perfect graph classes
- Parameterized algorithms
- Title not available (Why is that?)
- Recent developments on graphs of bounded clique-width
- A generalization of Villarreal's result for unmixed tripartite graphs
- Well-covered claw-free graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Partitions of graphs into one or two independent sets and cliques
- New graph classes of bounded clique-width
- List Partitions
- Very well covered graphs
- Complexity results for well‐covered graphs
- Monadic second-order evaluations on tree-decomposable graphs
- Title not available (Why is that?)
- List matrix partitions of chordal graphs
- Title not available (Why is that?)
- Well-covered graphs and extendability
- Graph-Theoretic Concepts in Computer Science
- Parameterized algorithms on perfect graphs for deletion to \((r,\ell)\)-graphs
- On the (parameterized) complexity of recognizing well-covered \((r,\ell)\)-graphs
- Unmixed r-partite graphs
- Machine characterizations for parameterized complexity classes beyond para-NP
Cited In (9)
- On the complexity of coloring ‐graphs
- Partitions and well-coveredness: the graph sandwich problem
- On the probe problem for \((r,\ell )\)-well-coveredness
- Computing well-covered vector spaces of graphs using modular decomposition
- Recognizing well-dominated graphs is coNP-complete
- Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs
- Mind the independence gap
- On the (parameterized) complexity of recognizing well-covered \((r,\ell)\)-graphs
- On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity
This page was built for publication: On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1784741)
