Graph bandwidth of weighted caterpillars
DOI10.1016/J.TCS.2006.07.015zbMATH Open1110.68110OpenAlexW2035656984MaRDI QIDQ860873FDOQ860873
Authors: Mingen Lin, Zhiyong Lin, Jinhui Xu 
Publication date: 9 January 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2006.07.015
Recommendations
- Algorithmic Applications in Management
- scientific article; zbMATH DE number 3859182
- Bandwidth of chain graphs
- Bounding the bandwidths for graphs
- Edge-Bandwidth of Graphs
- scientific article; zbMATH DE number 3963886
- On bandwidth sums of graphs
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Approximating the bandwidth of caterpillars
- On the size of graphs of a given bandwidth
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- The NP-completeness of the bandwidth minimization problem
- Bandwidth of chain graphs
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- The Bandwidth of Caterpillars with Hairs of Length 1 and 2
- Complexity Results for Bandwidth Minimization
- An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
- Approximating layout problems on random geometric graphs
- The bandwidth problem for graphs and matrices—a survey
- Approximating the bandwidth via volume respecting embeddings
- Improved bandwidth approximation for trees and chordal graphs
- Bandwidth Minimization: An approximation algorithm for caterpillars
Cited In (9)
- Algorithmic Applications in Management
- The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete
- An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion
- A quartic kernel for pathwidth-one vertex deletion
- Multilevel Bandwidth and Radio Labelings of Graphs
- Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
- Bandwidth Minimization: An approximation algorithm for caterpillars
- Euclidean networks with a backbone and a limit theorem for minimum spanning caterpillars
- An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
This page was built for publication: Graph bandwidth of weighted caterpillars
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q860873)
