Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time

DOI10.1137/0601042MaRDI QIDQ3960121zbMATH OpenOpenAlexFDO

Authors James B. Saxe

Publication date 1980

Published in SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0601042

zbMATH Keywords

bandwidth of a graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• Complexity Results for Bandwidth Minimization
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Some simplified NP-complete graph problems
• The NP-completeness of the bandwidth minimization problem

Cited in

(45)

• Bandwidths and profiles of trees
• Graph theoretic closure properties of the family of boundary NLC graph languages
• On the problem of bandsize
• Finding the minimum bandwidth of an interval graph
• Bounds on the convex label number of trees
• The complexity of minimizing wire lengths in VLSI layouts
• Optimal linear labelings and eigenvalues of graphs
• On the complexity of tree embedding problems
• Approximating the bandwidth via volume respecting embeddings
• Hardness results on the gapped consecutive-ones property problem
• Bandwidth contrained NP-complete problems
• Bandwidth and pebbling
• The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete
• Token sliding on split graphs
• From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability
• Approximating the bandwidth of caterpillars
• Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
• On the gapped consecutive-ones property
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• An exponential time 2-approximation algorithm for bandwidth
• Topological Bandwidth
• Linear arrangement problems on recursively partitioned graphs
• Bandwidth Minimization: An approximation algorithm for caterpillars
• Self‐clique graphs and matrix permutations
• Computing k-atomicity in polynomial time
• Intervalizing \(k\)-colored graphs
• Retracting Graphs to Cycles
• Critical elements in combinatorially closed families of graph classes
• On semidefinite programming bounds for graph bandwidth
• Faster Exact Bandwidth
• Algorithmic uses of the Feferman-Vaught theorem
• Hardness results for approximating the bandwidth
• Bandwidth and profile minimization
• Bandwidth on AT-free graphs
• Parameterized problems complete for nondeterministic FPT time and logarithmic space
• Two-Dimensional partitioning problems
• 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
• Recognizing 2-layer and outer k-planar graphs
• Linear layouts revisited: stacks, queues, and exact algorithms
• Undecidability of the bandwidth problem on linear graph languages
• The complexity of finding uniform emulations on paths and ring networks

This page was built for publication: Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3960121)