Satgraphs and independent domination. I

DOI10.1016/j.tcs.2005.08.038zbMath1086.68048MaRDI 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 algorithm; satisfiability problem; perfect graphs; NP-complete; forbidden induced subgraph characterization; hereditary class of graphs; independent domination problem; polar graphs; satgraphs

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Satgraphs and independent domination. I, Independent domination in hereditary classes, Polar graphs and maximal independent sets, On the inapproximability of independent domination in \(2P_3\)-free perfect graphs, NP-hard graph problems and boundary classes of graphs, Polar SAT and related graphs

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