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

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

Cited in

(43)

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

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)