A faster algorithm for dominating set analyzed by the potential method

DOI10.1007/978-3-642-28050-4_4MaRDI QIDQ2891336zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Automata, Languages and Programming
• Design by measure and conquer. A faster exact algorithm for dominating set
• A measure \& conquer approach for the analysis of exact algorithms
• Algorithms and Computation
• Exact algorithms for dominating set

Cites work

• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Algorithms for maximum independent sets
• Automata, Languages and Programming
• Design by measure and conquer. A faster exact algorithm for dominating set
• Exact algorithms for finding minimum transversals in rank-3 hypergraphs
• Exact exponential algorithms.
• Graph-Theoretic Concepts in Computer Science
• Inclusion/Exclusion Meets Measure and Conquer
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms

Cited in

(28)

• 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 \textsc{Upper Domination}: a parameterised perspective
• A measure \& conquer approach for the analysis of exact algorithms
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• scientific article; zbMATH DE number 1320677 (Why is no real title available?)
• Exact algorithms for Kayles
• Design by measure and conquer. A faster exact algorithm for dominating set
• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
• Improved bounds for online dominating sets of trees
• Exact algorithms for minimum weighted dominating induced matching
• Automata, Languages and Programming
• Faster graph coloring in polynomial space
• Further improvements for SAT in terms of formula length
• Exact and heuristic algorithms for the domination problem
• A hybrid population-based algorithm for solving the minimum dominating set problem
• A piecewise approach for the analysis of exact algorithms
• Algorithms for minimum membership dominating set problem
• Exact exponential algorithms for clustering problems
• Enumerating minimal connected dominating sets
• Enumerating minimal connected dominating sets
• A piecewise approach for the analysis of exact algorithms
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover

This page was built for publication: A faster algorithm for dominating set analyzed by the potential method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2891336)