Bandwidth of chain graphs

DOI10.1016/S0020-0190(98)00173-2zbMath1339.05393OpenAlexW2043400700MaRDI QIDQ293476

Dieter Kratsch, Haiko Müller, Ton Kloks

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098001732?np=y

zbMATH Keywords

bandwidthgraph algorithmschain graphs

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (20)

Linear structure of bipartite permutation graphs and the longest path problem ⋮ Hardness results of connected power domination for bipartite graphs and chordal graphs ⋮ Graph bandwidth of weighted caterpillars ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Permutation bigraphs and interval containments ⋮ Bichain graphs: geometric model and universal graphs ⋮ Bandwidth of convex bipartite graphs and related graphs ⋮ A note on maximum differential coloring of planar graphs ⋮ Minimal classes of graphs of unbounded clique-width ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ The Maximum Binary Tree Problem. ⋮ ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ Secure total domination in chain graphs and cographs ⋮ Bounds on mincut for Cayley graphs over Abelian groups ⋮ Bandwidth of Bipartite Permutation Graphs in Polynomial Time ⋮ The maximum binary tree problem ⋮ Bandwidth of bipartite permutation graphs in polynomial time ⋮ BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION

Cites Work

• Unnamed Item
• Bandwidth of theta graphs with short paths
• The NP-completeness of the bandwidth minimization problem
• Beyond NP-completeness for problems of bounded width (extended abstract)
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Representation of a finite graph by a set of intervals on the real line
• Computing the Bandwidth of Interval Graphs
• Node-Deletion Problems on Bipartite Graphs
• 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
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques

This page was built for publication: Bandwidth of chain graphs