Space and time complexity of exact algorithms: Some open problems

DOI10.1007/978-3-540-28639-4_25MaRDI 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

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

Cited in

(32)

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

This page was built for publication: Space and time complexity of exact algorithms: Some open problems

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