A Faster Algorithm for Dominating Set Analyzed by the Potential Method
From MaRDI portal
Publication:2891336
DOI10.1007/978-3-642-28050-4_4zbMath1352.68111MaRDI QIDQ2891336
Publication date: 15 June 2012
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-28050-4_4
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Unnamed Item, Unnamed Item, Faster graph coloring in polynomial space, Further improvements for SAT in terms of formula length, Minimal dominating sets in graph classes: combinatorial bounds and enumeration, Exact algorithms for Kayles, Exact algorithms for minimum weighted dominating induced matching, Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover, The many facets of upper domination, An improved exact algorithm for minimum dominating set in chordal graphs, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, Inclusion/exclusion meets measure and conquer, Exact algorithms for weak Roman domination, Solving Capacitated Dominating Set by using covering by subsets and maximum matching, On the Complexity Landscape of the Domination Chain, Algorithmic Aspects of Upper Domination: A Parameterised Perspective
Cites Work
- A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
- Exact exponential algorithms.
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
- Inclusion/Exclusion Meets Measure and Conquer
- Algorithms for maximum independent sets
- Exact algorithms for finding minimum transversals in rank-3 hypergraphs
- Graph-Theoretic Concepts in Computer Science
- Automata, Languages and Programming
- Unnamed Item
