A Moderately Exponential Time Algorithm for Full Degree Spanning Tree

DOI10.1007/978-3-540-79228-4_42zbMath1139.68391OpenAlexW2023638076MaRDI QIDQ3502671

Saket Saurabh, Serge Gaspers, Alexey A. Stepanov

Publication date: 27 May 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79228-4_42

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems ⋮ On the directed full degree spanning tree problem ⋮ On the Directed Degree-Preserving Spanning Tree Problem

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• A note on the complexity of the chromatic number problem
• Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
• Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
• Fourier meets M\"{o}bius: fast subset convolution
• Measure and conquer
• On Local Search and Placement of Meters in Networks
• Solving Connected Dominating Set Faster Than 2 n
• An algorithm for the chromatic number of a graph
• Automata, Languages and Programming
• Exact Computation of Maximum Induced Forest

This page was built for publication: A Moderately Exponential Time Algorithm for Full Degree Spanning Tree