Satgraphs and independent domination. I

DOI10.1016/j.tcs.2005.08.038zbMath1086.68048OpenAlexW2017593566MaRDI QIDQ818113

Igor Edm. 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

polynomial-time algorithmsatisfiability problemperfect graphsNP-completeforbidden induced subgraph characterizationhereditary class of graphsindependent domination problempolar graphssatgraphs

Mathematics Subject Classification ID

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

Related Items (18)

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

Cites Work

• Dominating sets for split and bipartite graphs
• Satgraphs and independent domination. I
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• Geometric algorithms and combinatorial optimization.
• Generalized split graphs and Ramsey numbers
• Progress on perfect graphs
• \(r\)-bounded \(k\)-complete bipartite bihypergraphs and generalized split graphs
• Partitioning permutations into increasing and decreasing subsequences
• Complexity results for well‐covered graphs
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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