Mind the independence gap
DOI10.1016/j.disc.2020.111943zbMath1443.05141arXiv1812.05316OpenAlexW3021108537MaRDI QIDQ776261
Ademir Hujdurović, Tınaz Ekim, Martin Milanič, Didem Gözüpek
Publication date: 8 July 2020
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1812.05316
polynomial-time algorithmindependent dominating setNP-hard problemmaximal independent setwell-covered graphhereditary independence gap
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On graphs with maximal independent sets of few sizes, minimum degree at least 2, and girth at least 7
- Satgraphs and independent domination. I
- On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
- Some results on graphs without long induced paths
- Clustering and domination in perfect graphs
- On maximal independent sets of vertices in claw-free graphs
- The ellipsoid method and its consequences in combinatorial optimization
- Independent domination in chordal graphs
- Well-covered graphs and extendability
- A characterization of graphs of girth eight or more with exactly two sizes of maximal independent sets
- The structure of well-covered graphs and the complexity of their recognition problems
- Independent domination in finitely defined classes of graphs
- Graphs vertex-partitionable into strong cliques
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- Linear time solvable optimization problems on graphs of bounded clique-width
- Independent domination in finitely defined classes of graphs: polynomial algorithms
- On graphs having maximal independent sets of exactly \(t\) distinct cardinalities
- Normal hypergraphs and the perfect graph conjecture
- Edge Dominating Sets in Graphs
- Complexity results for well‐covered graphs
- Independent Sets in Asteroidal Triple-Free Graphs
- WELL-COVERED GRAPHS: A SURVEY
- Robust algorithms for restricted domains
- On Almost Well-Covered Graphs of Girth at Least 6
- Recognizing Greedy Structures
- Well covered simplicial, chordal, and circular arc graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
This page was built for publication: Mind the independence gap
