Solving connected dominating set faster than \(2^n\)

DOI10.1007/s00453-007-9145-zzbMath1170.68030OpenAlexW2040813792WikidataQ60488749 ScholiaQ60488749MaRDI QIDQ958203

Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch

Publication date: 2 December 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9145-z

zbMATH Keywords

NP-hard problemconnected dominating setmaximum leaf spanning treeexponential-time exact algorithm

Mathematics Subject Classification ID

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

Related Items (38)

Computational approaches for zero forcing and related problems ⋮ FPT algorithms and kernels for the directed \(k\)-leaf problem ⋮ Searching for a cycle with maximum coverage in undirected graphs ⋮ Computing optimal Steiner trees in polynomial space ⋮ Robust Connectivity of Graphs on Surfaces ⋮ Enumeration of minimal tropical connected sets ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Connected power domination in graphs ⋮ Max-leaves spanning tree is APX-hard for cubic graphs ⋮ Solving target set selection with bounded thresholds faster than \(2^n\) ⋮ An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set} ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Domination and its variants in split graphs \(-\text{P}\) versus NPC dichotomy ⋮ An exact algorithm for connected red-blue dominating set ⋮ An exact exponential-time algorithm for the directed maximum leaf spanning tree problem ⋮ Solving Capacitated Dominating Set by using covering by subsets and maximum matching ⋮ Computing Minimum k-Connected m-Fold Dominating Set in General Graphs ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ On partitioning a graph into two connected subgraphs ⋮ A new algorithm for finding trees with many leaves ⋮ An exact algorithm for the maximum leaf spanning tree problem ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ Inclusion/exclusion meets measure and conquer ⋮ On parameterized independent feedback vertex set ⋮ A linear kernel for a planar connected dominating set ⋮ FPT algorithms for connected feedback vertex set ⋮ Constructing a spanning tree with many leaves ⋮ Complexity and computation of connected zero forcing ⋮ Below All Subsets for Minimal Connected Dominating Set ⋮ Layered graphs: applications and algorithms ⋮ Linear separation of connected dominating sets in graphs ⋮ Partitioning Graphs into Connected Parts ⋮ Near-Optimal Dominating Sets via Random Sampling ⋮ Partitioning graphs into connected parts ⋮ Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set ⋮ On Finding Directed Trees with Many Leaves ⋮ On connected dominating sets of restricted diameter

Cites Work

• Enumerating maximal independent sets with applications to graph colouring.
• An improved deterministic local search algorithm for 3-SAT
• Approximation algorithms for connected dominating sets
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Which problems have strongly exponential complexity?
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Primal-dual algorithms for connected facility location problems
• A note on the complexity of minimum dominating set
• A Dynamic Programming Approach to Sequencing Problems
• Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
• Simpler and better approximation algorithms for network design
• Measure and conquer
• Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
• Algorithms for maximum independent sets
• 3-coloring in time
• Parameterized and Exact Computation
• A Faster Algorithm for the Steiner Tree Problem
• Automata, Languages and Programming
• Automata, Languages and Programming
• STACS 2005
• Graph-Theoretic Concepts in Computer Science
• Automata, Languages and Programming
• Exact Computation of Maximum Induced Forest
• Algorithms and Data Structures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Solving connected dominating set faster than \(2^n\)