Satgraphs and independent domination. I

DOI10.1016/J.TCS.2005.08.038MaRDI QIDQ818113zbMATH OpenOpenAlexFDO

Authors I.È. Zverovich

Publication date 24 March 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.08.038

zbMATH Keywords

forbidden induced subgraph characterizationhereditary class of graphsindependent domination problemNP-completeperfect graphspolar graphspolynomial-time algorithmsatgraphssatisfiability problem

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Independent domination in hereditary classes
• Polar SAT and related graphs
• Independent domination in finitely defined classes of graphs: polynomial algorithms
• Independent domination in finitely defined classes of graphs
• More results on weighted independent domination

Cites work

• \(r\)-bounded \(k\)-complete bipartite bihypergraphs and generalized split graphs
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• Complexity results for well‐covered graphs
• Dominating sets for split and bipartite graphs
• Generalized split graphs and Ramsey numbers
• Geometric algorithms and combinatorial optimization.
• scientific article; zbMATH DE number 434906 (Why is no real title available?)
• scientific article; zbMATH DE number 4204394 (Why is no real title available?)
• scientific article; zbMATH DE number 3977053 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1455118 (Why is no real title available?)
• scientific article; zbMATH DE number 2154974 (Why is no real title available?)
• Partitioning permutations into increasing and decreasing subsequences
• Progress on perfect graphs
• Satgraphs and independent domination. I
• The complexity of theorem-proving procedures

Cited in

(19)

• On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
• Sum-perfect graphs
• Sparse regular induced subgraphs in \(2P_3\)-free graphs
• Independent domination in finitely defined classes of graphs: polynomial algorithms
• Independent domination versus weighted independent domination
• More results on weighted independent domination
• NP-hard graph problems and boundary classes of graphs
• Polar SAT and related graphs
• (2/2/3)-SAT problem and its applications in dominating set problems
• Combinatorics and algorithms for quasi-chain graphs
• On efficient domination for some classes of \(H\)-free chordal graphs
• Combinatorics and algorithms for quasi-chain graphs
• Treewidth versus clique number. II: Tree-independence number
• On 3-degree 4-chordal graphs
• Maximum regular induced subgraphs in 2P₃-free graphs
• Mind the independence gap
• Satgraphs and independent domination. I
• Independent domination in hereditary classes
• Polar graphs and maximal independent sets

This page was built for publication: Satgraphs and independent domination. I

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