Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
From MaRDI portal
Publication:3960121
DOI10.1137/0601042zbMath0496.68032OpenAlexW2039451540MaRDI QIDQ3960121
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Graph theoretic closure properties of the family of boundary NLC graph languages, The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete, On the problem of bandsize, Finding the minimum bandwidth of an interval graph, Bandwidth Minimization: An approximation algorithm for caterpillars, On semidefinite programming bounds for graph bandwidth, Faster Exact Bandwidth, Bounds on the convex label number of trees, From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability, The complexity of minimizing wire lengths in VLSI layouts, Approximating the bandwidth of caterpillars, Algorithmic uses of the Feferman-Vaught theorem, Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}, Hardness results for approximating the bandwidth, Linear arrangement problems on recursively partitioned graphs, Bandwidth and profile minimization, Undecidability of the bandwidth problem on linear graph languages, The complexity of finding uniform emulations on paths and ring networks, Bandwidth on AT-free graphs, Computing $k$-Atomicity in Polynomial Time, Two-Dimensional partitioning problems, Approximation algorithms for the bandwidth minimization problem for a large class of trees, Intervalizing k-colored graphs, Optimal linear labelings and eigenvalues of graphs, The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete, Hardness results on the gapped consecutive-ones property problem, On the complexity of tree embedding problems, Token sliding on split graphs, Self‐clique graphs and matrix permutations, Retracting Graphs to Cycles, Bandwidth contrained NP-complete problems, An Exponential Time 2-Approximation Algorithm for Bandwidth, Approximating the bandwidth via volume respecting embeddings, Bandwidth and pebbling, Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces, On the Gapped Consecutive-Ones Property, Critical elements in combinatorially closed families of graph classes, Topological Bandwidth, Bandwidths and profiles of trees
Cites Work
