Solving Connected Dominating Set Faster Than 2 n
From MaRDI portal
Publication:5385982
DOI10.1007/11944836_16zbMath1170.68545OpenAlexW2134595729MaRDI QIDQ5385982
Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch
Publication date: 17 April 2008
Published in: FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11944836_16
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 (6)
A Moderately Exponential Time Algorithm for Full Degree Spanning Tree ⋮ Solving Capacitated Dominating Set by using covering by subsets and maximum matching ⋮ An exact algorithm for the minimum dominating clique problem ⋮ Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching ⋮ Better Algorithms and Bounds for Directed Maximum Leaf Problems ⋮ A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
This page was built for publication: Solving Connected Dominating Set Faster Than 2 n
