Parameterized and Exact Computation

DOI10.1007/B100584zbMath1104.68520OpenAlexW2475962691MaRDI QIDQ5311520

Gerhard J. Woeginger

Publication date: 23 August 2005

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

Full work available at URL: https://doi.org/10.1007/b100584

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (23)

Computing optimal Steiner trees in polynomial space ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ On comparing algorithms for the maximum clique problem ⋮ Space saving by dynamic algebraization based on tree-depth ⋮ Exact Algorithms for Edge Domination ⋮ Exact algorithms for dominating set ⋮ Exact algorithms for edge domination ⋮ Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems ⋮ Feedback Vertex Sets in Tournaments ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ An exact algorithm for the minimum dominating clique problem ⋮ An exact algorithm for MAX-CUT in sparse graphs ⋮ Solving connected dominating set faster than \(2^n\) ⋮ Exact algorithms for exact satisfiability and number of perfect matchings ⋮ Scheduling partially ordered jobs faster than \(2^n\) ⋮ Finding a dominating set on bipartite graphs ⋮ Unnamed Item ⋮ Efficient algorithms for clique problems ⋮ Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems ⋮ Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights ⋮ On two techniques of combining branching and treewidth ⋮ Planar k-Path in Subexponential Time and Polynomial Space ⋮ Moderate exponential-time algorithms for scheduling problems

This page was built for publication: Parameterized and Exact Computation