A simple linear-time algorithm for the recognition of bandwidth-2 biconnected graphs

DOI10.1016/0020-0190(93)90206-OMaRDI QIDQ1802068zbMATH OpenOpenAlexFDO

Authors Fillia Makedon, Dafna Sheinwald, Yaron Wolfsthal

Publication date 8 August 1993

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

Full work available at URL https://doi.org/10.1016/0020-0190(93)90206-o

zbMATH Keywords

bandwidthVLSI layoutgraph recognition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Applications of graph theory to circuits and networks (94C15)

Recommendations

• On bandwidth-2 graphs
• Testing Bandwidth k for k-Connected Graphs
• Bandwidth of Bipartite Permutation Graphs
• Finding the minimum bandwidth of an interval graph
• scientific article; zbMATH DE number 3914372

Cites work

• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• Complexity Results for Bandwidth Minimization
• Flit-serial packet routing on meshes and tori
• One-Page Book Embedding under Vertex-Neighborhood Constraints
• Two-page book embedding of trees under vertex-neighborhood constraints

Cited in

(2)

• On bandwidth-2 graphs
• Testing Bandwidth k for k-Connected Graphs

This page was built for publication: A simple linear-time algorithm for the recognition of bandwidth-2 biconnected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1802068)