Open problems around exact algorithms
From MaRDI portal
Publication:2473037
DOI10.1016/j.dam.2007.03.023zbMath1165.90613OpenAlexW2168336253MaRDI QIDQ2473037
Publication date: 26 February 2008
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2007.03.023
Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items (20)
Improved Information Set Decoding for Code-Based Cryptosystems with Constrained Memory ⋮ Solving the job-shop scheduling problem optimally by dynamic programming ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ On comparing algorithms for the maximum clique problem ⋮ Improved bounds for minimal feedback vertex sets in tournaments ⋮ Complement, Complexity, and Symmetric Representation ⋮ Solving larger maximum clique problems using parallel quantum annealing ⋮ Exact algorithms for dominating set ⋮ Exact algorithms for finding longest cycles in claw-free graphs ⋮ An ETH-Tight Exact Algorithm for Euclidean TSP ⋮ Feedback Vertex Sets in Tournaments ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP ⋮ Sex-equal stable matchings: complexity and exact algorithms ⋮ Scheduling partially ordered jobs faster than \(2^n\) ⋮ Unnamed Item ⋮ Fixed-parameter tractability results for feedback set problems in tournaments ⋮ Improved upper bounds for vertex cover ⋮ A note on the intersection property for flat boxes and boxicity in \(\mathbb R^d\) ⋮ Faster graph coloring in polynomial space ⋮ Exact algorithms for counting 3-colorings of graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A finite-difference sieve to count paths and cycles by length
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Inclusion and exclusion algorithm for the Hamiltonian path problem
- On the complexity of fixed parameter clique and dominating set
- Matrix multiplication via arithmetic progressions
- NP-completeness of some problems concerning voting games
- Dynamic programming meets the principle of inclusion and exclusion
- A note on the complexity of the chromatic number problem
- A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
- Fast rectangular matrix multiplication and applications
- Algorithms to count paths and cycles
- On enumerating all minimal solutions of feedback problems
- Rectangular matrix multiplication revisited
- Faster algorithms for computing power indices in weighted voting games
- On a class of \(O(n^ 2)\) problems in computational geometry
- The searching over separators strategy to solve some NP-hard problems in subexponential time
- A \(2^{|E|/4}\)-time algorithm for MAX-CUT
- A Dynamic Programming Approach to Sequencing Problems
- The complexity of the travelling repairman problem
- Algorithms for maximum independent sets
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
- Computing Partitions with Applications to the Knapsack Problem
- Finding a Maximum Independent Set
- Finding a Minimum Circuit in a Graph
- Color-coding
- Hamilton Paths in Grid Graphs
- Automata, Languages and Programming
- On maximal transitive subtournaments
- Algorithms and Data Structures
This page was built for publication: Open problems around exact algorithms
