Exact and approximate bandwidth
From MaRDI portal
Publication:708223
DOI10.1016/J.TCS.2010.06.018zbMATH Open1207.68443OpenAlexW2076595213MaRDI QIDQ708223FDOQ708223
Authors: Marek Cygan, Marcin Pilipczuk 
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
Recommendations
Cites Work
- Complexity of Finding Embeddings in a k-Tree
- Title not available (Why is that?)
- Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Complexity Results for Bandwidth Minimization
- Fourier meets M\"{o}bius: fast subset convolution
- Approximating the bandwidth of caterpillars
- Title not available (Why is that?)
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- Even faster exact bandwidth
- An exponential time 2-approximation algorithm for bandwidth
- Title not available (Why is that?)
- Counting Subgraphs via Homomorphisms
- Exact and Approximate Bandwidth
- Faster Exact Bandwidth
- Title not available (Why is that?)
Cited In (38)
- An exponential time 2-approximation algorithm for bandwidth
- An exponential time 2-approximation algorithm for bandwidth
- Bandwidth and distortion revisited
- Exponential approximation schemata for some network design problems
- Faster Exact Bandwidth
- An exact algorithm for minimum distortion embedding
- A generic convolution algorithm for join operations on tree decompositions
- Complement, complexity, and symmetric representation
- Even faster exact bandwidth
- Algorithms for dominating clique problems
- More effort towards multiagent knapsack
- In)approximability of Maximum Minimal FVS
- Tractabilities and intractabilities on geometric intersection graphs
- Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
- Super-polynomial approximation branching algorithms
- Computing generalized convolutions faster than brute force
- Even more effort towards improved bounds and fixed-parameter tractability for multiwinner rules
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- Gerrymandering on graphs: computational complexity and parameterized algorithms
- Fast Algorithms for Join Operations on Tree Decompositions
- (In)approximability of maximum minimal FVS
- Title not available (Why is that?)
- Time-approximation trade-offs for inapproximable problems
- On the parameterized complexity of b-\textsc{chromatic number}
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- When polynomial approximation meets exact computation
- New tools and connections for exponential-time approximation
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
- Parameterized approximation via fidelity preserving transformations
- Exact and Approximate Bandwidth
- When polynomial approximation meets exact computation
- Maximum Bandwidth Under Edge Addition
- On subexponential and FPT-time inapproximability
- Sparsification and subexponential approximation
- Moderately exponential time and fixed parameter approximation algorithms
- Scheduling partially ordered jobs faster than \(2^n\)
- Title not available (Why is that?)
This page was built for publication: Exact and approximate bandwidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q708223)
