Sort and Search: exact algorithms for generalized domination

DOI10.1016/J.IPL.2009.03.023MaRDI QIDQ989487zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff

Publication date 20 August 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2009.03.023

zbMATH Keywords

exact algorithmsgraph algorithmsdominationsortingsearching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Branch and Recharge: Exact Algorithms for Generalized Domination
• Parameterized complexity of generalized domination problems
• Parameterized Complexity of Generalized Domination Problems
• Branch and recharge: exact algorithms for generalized domination
• Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs

Cites work

• [article; zbMATH DE number 1095171 (Why is no real title available?)]
• [article; zbMATH DE number 1099195 (Why is no real title available?)]
• [article; zbMATH DE number 1161563 (Why is no real title available?)]
• [article; zbMATH DE number 1953201 (Why is no real title available?)]
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• Algorithms for four variants of the exact satisfiability problem
• Computing Partitions with Applications to the Knapsack Problem
• Mod-2 independence and domination in graphs
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory

Cited in

(6)

• Parameterized complexity of generalized domination problems
• Branch and Recharge: Exact Algorithms for Generalized Domination
• scientific article; zbMATH DE number 1320677 (Why is no real title available?)
• Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity
• Exact algorithms for problems related to the densest \(k\)-set problem
• Branch and recharge: exact algorithms for generalized domination

This page was built for publication: Sort and Search: exact algorithms for generalized domination

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