Channel assignment on graphs of bounded treewidth

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

Colin J. H. McDiarmid, Bruce A. Reed

Publication date: 5 January 2004

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

Full work available at URL: https://doi.org/10.1016/s0012-365x(03)00236-x

zbMATH Keywords

Graph colouringChannel assignmentBounded treewidth

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (10)

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

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

This page was built for publication: Channel assignment on graphs of bounded treewidth