Independent domination in finitely defined classes of graphs: polynomial algorithms

DOI10.1016/J.DAM.2013.08.030MaRDI QIDQ2255037zbMATH OpenOpenAlexFDO

Authors Vadim 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

zbMATH Keywords

polynomial-time algorithmindependent dominationfinitely defined class of graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Independent domination in finitely defined classes of graphs
• Independent domination in hereditary classes
• Satgraphs and independent domination. I
• scientific article; zbMATH DE number 468640
• Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time

Cites work

• scientific article; zbMATH DE number 3908482 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
• Augmenting graphs for independent sets
• Domination in convex and chordal bipartite graphs
• Edge Dominating Sets in Graphs
• Independent domination in chordal graphs
• Independent domination in finitely defined classes of graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• Modular decomposition and transitive orientation
• On algorithms for (\(P_5\), gem)-free graphs
• On diameters and radii of bridged graphs
• On finding augmenting graphs
• On independent vertex sets in subclasses of apple-free graphs
• On maximum independent sets in \(P_{5}\)-free graphs
• On the X-join decomposition for undirected graphs
• On the vertex packing problem
• Satgraphs and independent domination. I
• Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• Stable sets in \(k\)-colorable \(P_{5}\)-free graphs
• The weighted independent domination problem is NP-complete for chordal graphs
• Transitiv orientierbare Graphen
• \(P_{5}\)-free augmenting graphs and the maximum stable set problem

Cited in

(11)

• scientific article; zbMATH DE number 6460018 (Why is no real title available?)
• Mind the independence gap
• Satgraphs and independent domination. I
• Independent domination versus weighted independent domination
• Independent domination in finitely defined classes of graphs
• A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• Iterative construction of the minimum independent dominating sets in hypercube graphs
• More results on weighted independent domination
• Complexity of the approximation of the independent dominating set problem in the class of \(2P_3\)-free perfect graphs
• An algorithm for calculating the independence and vertex-cover polynomials of a graph
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems

This page was built for publication: Independent domination in finitely defined classes of graphs: polynomial algorithms

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