Interval degree and bandwidth of a graph

DOI10.1016/S0166-218X(02)00574-7zbMath1021.05087OpenAlexW2134452793MaRDI QIDQ1406031

Petr A. Golovach, Fedor V. Fomin

Publication date: 9 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00574-7

zbMATH Keywords

bandwidthinterval graphpathwidthAT-free claw-free graphinterval degree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Graph drawings with few slopes ⋮ Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Degree bounds for linear discrepancy of interval orders and disconnected posets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. I. Excluding a forest
• Interval graphs and searching
• The vertex separation number of a graph equals its path-width
• A partial k-arboretum of graphs with bounded treewidth
• The vertex separation and search number of a graph
• Chordal completions of planar graphs
• Treewidth. Computations and approximations
• Approximating the bandwidth via volume respecting embeddings
• On the powers of graphs with bounded asteroidal number
• Triangulating graphs without asteroidal triples
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Representation of a finite graph by a set of intervals on the real line
• On interval graphs and matrice profiles
• Complexity of Finding Embeddings in a k-Tree
• The bandwidth problem for graphs and matrices—a survey
• Algorithmic Aspects of Vertex Elimination on Graphs
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs

This page was built for publication: Interval degree and bandwidth of a graph