Solving connected dominating set faster than \(2^n\)
type: Item
instance of: scholarly article
title: Solving connected dominating set faster than \(2^n\)
zbMATH Open document ID: 1170.68030
author: Fedor V. Fomin
author: Fabrizio Grandoni
author: Dieter Kratsch
published in: Algorithmica
publication date: 2008-12-02T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5377139
zbMATH Keywords: exponential-time exact algorithm
zbMATH Keywords: NP-hard problem
zbMATH Keywords: connected dominating set
zbMATH Keywords: maximum leaf spanning tree
Wikidata QID: Q60488749
MaRDI profile type: Publication
full work available at URL: s00453-007-9145-z
OpenAlex ID: W2040813792
cites work: 3-coloring in time
cites work: Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
cites work: Q5692521
cites work: An improved deterministic local search algorithm for 3-SAT
cites work: Enumerating maximal independent sets with applications to graph colouring.
cites work: A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
cites work: Algorithms and Data Structures
cites work: Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
cites work: Automata, Languages and Programming
cites work: Q3396567
cites work: Measure and conquer
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Q4198056
cites work: A note on the complexity of minimum dominating set
cites work: Approximation algorithms for connected dominating sets
cites work: Simpler and better approximation algorithms for network design
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: A Dynamic Programming Approach to Sequencing Problems
cites work: Which problems have strongly exponential complexity?
cites work: Q3395987
cites work: A Faster Algorithm for the Steiner Tree Problem
cites work: 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
cites work: Exact Computation of Maximum Induced Forest
cites work: Algorithms for maximum independent sets
cites work: STACS 2005
cites work: Primal-dual algorithms for connected facility location problems
cites work: Q4414647
cites work: Parameterized and Exact Computation
DOI: 10.1007/S00453-007-9145-Z
DBLP publication ID: journals/algorithmica/FominGK08
description: scientific article; zbMATH DE number 5377139