Parameterized and Exact Computation

DOI10.1007/B100584MaRDI QIDQ5311520zbMATH OpenOpenAlexFDO

Authors 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

Cited in

(32)

• New results on the mathematical foundations of asymptotic complexity analysis of algorithms via complexity spaces
• Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights
• Computing optimal Steiner trees in polynomial space
• Finding a dominating set on bipartite graphs
• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• Exact algorithms for dominating set
• Parameterized local search for vertex cover: when only the search radius is crucial
• Open problems around exact algorithms
• Exact algorithms for exact satisfiability and number of perfect matchings
• Efficient algorithms for clique problems
• scientific article; zbMATH DE number 5901113 (Why is no real title available?)
• An exact algorithm for MAX-CUT in sparse graphs
• On two techniques of combining branching and treewidth
• If the current clique algorithms are optimal, so is Valiant's parser
• Tight space bounds for \(\ell\)-exclusion
• Moderate exponential-time algorithms for scheduling problems
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Feedback vertex sets in tournaments
• On comparing algorithms for the maximum clique problem
• An exact algorithm for the minimum dominating clique problem
• Exact Algorithms for Edge Domination
• On the Space Complexity of Parameterized Problems
• Planar k-path in subexponential time and polynomial space
• scientific article; zbMATH DE number 7525510 (Why is no real title available?)
• Faster Steiner Tree Computation in Polynomial-Space
• scientific article; zbMATH DE number 549085 (Why is no real title available?)
• Solving connected dominating set faster than \(2^n\)
• Space saving by dynamic algebraization based on tree-depth
• Exponential-time approximation schemes via compression
• Exact algorithms for edge domination
• Moderate exponential-time algorithms for scheduling problems
• Scheduling partially ordered jobs faster than \(2^n\)

This page was built for publication: Parameterized and Exact Computation

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