Channel assignment on graphs of bounded treewidth

DOI10.1016/S0012-365X(03)00236-XzbMath1029.05150MaRDI QIDQ1417576

Colin J. H. McDiarmid, Bruce A. Reed

Publication date: 5 January 2004

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

zbMATH Keywords

Graph colouring; Channel assignment; Bounded treewidth

Mathematics Subject Classification ID

05C90: Applications of graph theory

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

Related Items

Practical algorithms for MSO model-checking on tree-decomposable graphs, Parameterized complexity of coloring problems: treewidth versus vertex cover, Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs, An exact algorithm for the channel assignment problem, Parameterized complexity of distance labeling and uniform channel assignment problems, Bandwidth consecutive multicolorings of graphs, Generalized edge-colorings of weighted graphs, Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems, Fixed-Parameter Tractability of Treewidth and Pathwidth, THE GRAPH-BIN PACKING PROBLEM

Cites Work

• Easy problems for tree-decomposable graphs
• A linear time algorithm for finding tree-decompositions of small treewidth
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item