Exponential-time approximation (schemes) for vertex-ordering problems
From MaRDI portal
Cites work
- \(\ell ^2_2\) spreading metrics for vertex ordering problems
- A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
- A note on exact algorithms for vertex ordering problems on graphs
- A Remark on Stirling's Formula
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- An improved approximation ratio for the minimum linear arrangement problem
- Approximate monotone local search for weighted problems
- Approximating minimum feedback sets and multicuts in directed graphs
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Automata, Languages and Programming
- Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication
- Breaking the 2ⁿ barrier for 5-coloring and 6-coloring
- Breaking the all subsets barrier for min k-cut
- Computing directed pathwidth in O(1.89ⁿ) time
- Exact algorithms via monotone local search
- Exact and approximate bandwidth
- Exact and Approximate Digraph Bandwidth
- Exact exponential algorithms.
- Exponential-time approximation schemes via compression
- Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
- Faster exponential-time approximation algorithms using approximate monotone local search
- Finding a Minimum Circuit in a Graph
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Inapproximability of treewidth, one-shot pebbling, and related layout problems
- Independent set, induced matching, and pricing: connections and tight (subexponential time) approximation hardnesses
- Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
- New tools and connections for exponential-time approximation
- On approximating cutwidth and pathwidth
- On cutwidth parameterized by vertex cover
- On the hardness of approximating minimum vertex cover
- Optimal Linear Arrangement of Interval Graphs
- Optimally repurposing existing algorithms to obtain exponential-time approximations
- Pathwidth is NP-Hard for Weighted Trees
- Quantum speedups for exponential-time dynamic programming algorithms
This page was built for publication: Exponential-time approximation (schemes) for vertex-ordering problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7296645)
