Bandwidth of bipartite permutation graphs in polynomial time
type: Item
instance of: scholarly article
title: Bandwidth of bipartite permutation graphs in polynomial time
zbMATH Open document ID: 1209.05242
author: Pinar Heggernes
author: Dieter Kratsch
author: Daniel Meister
published in: Journal of Discrete Algorithms
publication date: 2009-12-10T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C62
zbMATH DE Number: 5645015
zbMATH Keywords: NP-complete problem
zbMATH Keywords: graph layout problem
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: bandwidth
zbMATH Keywords: bipartite permutation graphs
describes a project that uses: symrcm
MaRDI profile type: Publication
full work available at URL: j.jda.2008.11.001
OpenAlex ID: W2023657479
cites work: The Bandwidth of Caterpillars with Hairs of Length 1 and 2
cites work: Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
cites work: Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
cites work: On Exact Algorithms for Treewidth
cites work: Graph Classes: A Survey
cites work: Q4393480
cites work: Q4542524
cites work: Q2721963
cites work: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
cites work: Linear discrepancy and bandwidth
cites work: Q3664299
cites work: Q3328583
cites work: Q4952701
cites work: Bandwidth Minimization: An approximation algorithm for caterpillars
cites work: Computing the Bandwidth of Interval Graphs
cites work: Bandwidth of chain graphs
cites work: Approximating the Bandwidth for Asteroidal Triple-Free Graphs
cites work: Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
cites work: The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
cites work: The NP-completeness of the bandwidth minimization problem
cites work: Bipartite permutation graphs
cites work: An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
cites work: Q4004146
cites work: Q3839788
DOI: 10.1016/J.JDA.2008.11.001
Recommended article: Bandwidth of Bipartite Permutation Graphs in Polynomial Time
Recommended article: Bandwidth of Bipartite Permutation Graphs
Recommended article: Q2766686
Recommended article: Bandwidth of Convex Bipartite Graphs and Related Graphs
Recommended article: Bandwidth of convex bipartite graphs and related graphs
Recommended article: An extremal bandwidth problem for bipartite graphs
Recommended article: Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time
Recommended article: Bipartite permutation graphs with application to the minimum buffer size problem
Recommended article: Q4393299
description: scientific article; zbMATH DE number 5645015