Independent domination in finitely defined classes of graphs: polynomial algorithms
From MaRDI portal
Publication:2255037
DOI10.1016/J.DAM.2013.08.030zbMath1306.05184OpenAlexW2502941697MaRDI QIDQ2255037
Vadim V. Lozin, Raffaele Mosca, Christopher Purcell
Publication date: 6 February 2015
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2013.08.030
Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (5)
More results on weighted independent domination ⋮ Iterative construction of the minimum independent dominating sets in hypercube graphs ⋮ Independent domination versus weighted independent domination ⋮ Mind the independence gap ⋮ A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Augmenting graphs for independent sets
- On maximum independent sets in \(P_{5}\)-free graphs
- On algorithms for (\(P_5\), gem)-free graphs
- Satgraphs and independent domination. I
- On independent vertex sets in subclasses of apple-free graphs
- Domination in convex and chordal bipartite graphs
- On finding augmenting graphs
- Maximum independent sets in subclasses of \(P_{5}\)-free graphs
- Stable sets in \(k\)-colorable \(P_{5}\)-free graphs
- On diameters and radii of bridged graphs
- On the X-join decomposition for undirected graphs
- Independent domination in chordal graphs
- Modular decomposition and transitive orientation
- Independent domination in finitely defined classes of graphs
- An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
- \(P_{5}\)-free augmenting graphs and the maximum stable set problem
- Some results on maximum stable sets in certain \(P_{5}\)-free graphs
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- The weighted independent domination problem is NP-complete for chordal graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- On the vertex packing problem
- Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs
- Edge Dominating Sets in Graphs
- An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
- Transitiv orientierbare Graphen
This page was built for publication: Independent domination in finitely defined classes of graphs: polynomial algorithms
