Branch and recharge: exact algorithms for generalized domination

DOI10.1007/s00453-010-9418-9zbMath1244.68082OpenAlexW2156840525WikidataQ60488553 ScholiaQ60488553MaRDI QIDQ639293

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

Publication date: 20 September 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9418-9

zbMATH Keywords

NP-hard problemsexact exponential algorithmsgeneralized dominationbranch and recharge

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumerating maximal independent sets with applications to graph colouring.
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Sort and Search: exact algorithms for generalized domination
• A note on the complexity of the chromatic number problem
• New methods for 3-SAT decision and worst-case analysis
• Independent sets with domination constraints
• Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity
• Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
• Measure and conquer
• Branch and Recharge: Exact Algorithms for Generalized Domination
• Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• 3-coloring in time
• On the number of maximal bipartite subgraphs of a graph
• Combinatorial bounds via measure and conquer
• Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems
• Automata, Languages and Programming
• Parameterized Complexity of Generalized Domination Problems
• On cliques in graphs