The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
From MaRDI portal
Recommendations
- The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete
- scientific article; zbMATH DE number 1854238
- Bandwidth Minimization: An approximation algorithm for caterpillars
- scientific article; zbMATH DE number 1472394
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Approximating the bandwidth of caterpillars
- Upper and lower bounding procedures for the minimum caterpillar spanning problem
- Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
- On the minimum caterpillar problem in digraphs
- Bandwidth contrained NP-complete problems
Cites work
- Comparative Analysis of the Cuthill–McKee and the Reverse Cuthill–McKee Ordering Algorithms for Sparse Matrices
- Complexity Results for Bandwidth Minimization
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- scientific article; zbMATH DE number 3732090 (Why is no real title available?)
- scientific article; zbMATH DE number 3733986 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3410504 (Why is no real title available?)
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- The Bandwidth of Caterpillars with Hairs of Length 1 and 2
- The bandwidth problem for graphs and matrices—a survey
- The NP-completeness of the bandwidth minimization problem
Cited in
(61)- Bandwidth of bipartite permutation graphs in polynomial time
- A fixed-parameter tractability result for multicommodity demand flow in trees
- Min Cut is NP-complete for edge weighted trees
- Bandwidth of theta graphs with short paths
- Embedding ladders and caterpillars into the hypercube
- Interval degree and bandwidth of a graph
- Selected papers in honor of Manuel Blum on the occasion of his 60th birthday. Selected papers from the international conference in Theoretical Computer Science, Hong Kong, April 20-24, 1998
- Approximating the bandwidth via volume respecting embeddings
- Bandwidth and density for block graphs
- Tractabilities and intractabilities on geometric intersection graphs
- The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete
- Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
- On the bandwidth of the Kneser graph
- Approximating the bandwidth of caterpillars
- Cyclic bandwidth with an edge added
- Lower bounds for the bandwidth problem
- Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
- Approximating bandwidth by mixing layouts of interval graphs
- Bandwidth of chain graphs
- Packing of (0, 1)-matrices
- The Proper Interval Colored Graph problem for caterpillar trees
- Euclidean networks with a backbone and a limit theorem for minimum spanning caterpillars
- Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
- Random Generation and Enumeration of Proper Interval Graphs
- On the proper intervalization of colored caterpillar trees
- An exponential time 2-approximation algorithm for bandwidth
- An exponential time 2-approximation algorithm for bandwidth
- Bandwidth Minimization: An approximation algorithm for caterpillars
- Bandwidth of trees of diameter at most 4
- A combinatorial optimization algorithm for solving the branchwidth problem
- Bandwidth of convex bipartite graphs and related graphs
- scientific article; zbMATH DE number 1472394 (Why is no real title available?)
- A note on maximum differential coloring of planar graphs
- Grundy Distinguishes Treewidth from Pathwidth
- Line-distortion, bandwidth and path-length of a graph
- On semidefinite programming bounds for graph bandwidth
- Faster Exact Bandwidth
- Bandwidth of Bipartite Permutation Graphs in Polynomial Time
- Algorithmic Applications in Management
- Grundy distinguishes treewidth from pathwidth
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Bandwidth and topological bandwidth of graphs with few \(P_4\)'s
- Tangle bases: Revisited
- Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees
- Approximating the bandwidth for asteroidal triple-free graphs
- Hardness results for approximating the bandwidth
- Bandwidth and profile minimization
- Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
- Bandwidth on AT-free graphs
- Parameterized algorithms for minimum sum vertex cover
- Parameterized problems complete for nondeterministic FPT time and logarithmic space
- Approximation algorithms for the bandwidth minimization problem for a large class of trees
- Bandwidth parameterized by cluster vertex deletion number
- Bandwidth parameterized by cluster vertex deletion number
- Exact and approximate digraph bandwidth
- Parameterized algorithms for minimum sum vertex cover
- Exact and approximate bandwidth
- Equitable colorings of bounded treewidth graphs
- Graph bandwidth of weighted caterpillars
- Minimal proper interval completions
This page was built for publication: The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3026359)
