Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs

DOI10.1016/j.tcs.2015.07.052zbMath1332.05138OpenAlexW1056934671MaRDI QIDQ897950

Takao Nishizeki, Yuji Obata

Publication date: 8 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.07.052

zbMATH Keywords

approximation algorithmgraph coloringbandwidth consecutive multicoloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

A Simple 2-Approximation for Maximum-Leaf Spanning Tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Heuristics for the bandwidth colouring problem
• Three short proofs in graph theory
• Zero knowledge and the chromatic number
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Channel assignment on graphs of bounded treewidth
• On the span in channel assignment problems: Bounds, computing and counting
• Bandwidth consecutive multicolorings of graphs
• An evolutionary approach for bandwidth multicoloring problems
• Two genetic algorithms for the bandwidth multicoloring problem
• Approximation Algorithms for Bandwidth Consecutive Multicolorings
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• A linear 5-coloring algorithm of planar graphs
• Linear-time computability of combinatorial problems on series-parallel graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• Scheduling

This page was built for publication: Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs