Exact and approximate bandwidth
From MaRDI portal
Publication:708223
DOI10.1016/j.tcs.2010.06.018zbMath1207.68443OpenAlexW2076595213MaRDI QIDQ708223
Publication date: 11 October 2010
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.06.018
Related Items
Fast Algorithms for Join Operations on Tree Decompositions, On the parameterized complexity of b-\textsc{chromatic number}, Time-approximation trade-offs for inapproximable problems, Gerrymandering on graphs: computational complexity and parameterized algorithms, An exponential time 2-approximation algorithm for bandwidth, Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem, Exponential approximation schemata for some network design problems, Complement, Complexity, and Symmetric Representation, Parameterized approximation via fidelity preserving transformations, Even more effort towards improved bounds and fixed-parameter tractability for multiwinner rules, Super-polynomial approximation branching algorithms, Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, Bandwidth and distortion revisited, More effort towards multiagent knapsack, Computing generalized convolutions faster than brute force, Sparsification and subexponential approximation, When polynomial approximation meets exact computation, Approximating MAX SAT by moderately exponential and parameterized algorithms, Solving the 2-disjoint connected subgraphs problem faster than \(2^n\), Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}, Tractabilities and intractabilities on geometric intersection graphs, When polynomial approximation meets exact computation, In)approximability of Maximum Minimal FVS, Scheduling partially ordered jobs faster than \(2^n\), Algorithms for dominating clique problems, An exact algorithm for minimum distortion embedding, New tools and connections for exponential-time approximation, (In)approximability of maximum minimal FVS, On subexponential and FPT-time inapproximability, Moderately exponential time and fixed parameter approximation algorithms, A generic convolution algorithm for join operations on tree decompositions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating the bandwidth of caterpillars
- Beyond NP-completeness for problems of bounded width (extended abstract)
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- Even Faster Exact Bandwidth
- Fourier meets M\"{o}bius: fast subset convolution
- Exact and Approximate Bandwidth
- An Exponential Time 2-Approximation Algorithm for Bandwidth
- Complexity of Finding Embeddings in a k-Tree
- Complexity Results for Bandwidth Minimization
- Faster Exact Bandwidth
- Counting Subgraphs via Homomorphisms
