A Faster Algorithm for Dominating Set Analyzed by the Potential Method

DOI10.1007/978-3-642-28050-4_4zbMath1352.68111OpenAlexW1439548790MaRDI QIDQ2891336

Yoichi Iwata

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

Mathematics Subject Classification ID

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

Related Items (16)

Minimal dominating sets in graph classes: combinatorial bounds and enumeration ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Exact algorithms for weak Roman domination ⋮ Further improvements for SAT in terms of formula length ⋮ Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover ⋮ The many facets of upper domination ⋮ Solving Capacitated Dominating Set by using covering by subsets and maximum matching ⋮ Exact algorithms for Kayles ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ Inclusion/exclusion meets measure and conquer ⋮ On the Complexity Landscape of the Domination Chain ⋮ Unnamed Item ⋮ Faster graph coloring in polynomial space ⋮ An improved exact algorithm for minimum dominating set in chordal graphs ⋮ Algorithmic Aspects of Upper Domination: A Parameterised Perspective ⋮ Unnamed Item

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

This page was built for publication: A Faster Algorithm for Dominating Set Analyzed by the Potential Method