Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs

DOI10.1016/J.TCS.2015.07.052MaRDI QIDQ897950zbMATHOpenAlexFDO

Authors Yuji Obata, Takao Nishizeki

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

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

Recommendations

• Approximation algorithms for bandwidth consecutive multicolorings (extended abstract)
• Algorithms for bandwidth consecutive multicolorings of graphs (extended abstract)
• Bandwidth consecutive multicolorings of graphs
• Improving a family of approximation algorithms to edge color multigraphs
• Efficient bounds on a branch and bound algorithm for graph colouration
• scientific article; zbMATH DE number 7650095
• Experimental and Efficient Algorithms
• An asymptotic approximation scheme for multigraph edge coloring
• An asymptotic approximation scheme for multigraph edge coloring
• Approximation algorithms for multicoloring planar graphs and powers of square and triangular meshes

Cites work

• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• A linear 5-coloring algorithm of planar graphs
• An evolutionary approach for bandwidth multicoloring problems
• Approximation algorithms for bandwidth consecutive multicolorings (extended abstract)
• Bandwidth consecutive multicolorings of graphs
• Channel assignment on graphs of bounded treewidth
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• Heuristics for the bandwidth colouring problem
• Introduction to algorithms
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Linear-time computability of combinatorial problems on series-parallel graphs
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• On the span in channel assignment problems: Bounds, computing and counting
• Scheduling
• Three short proofs in graph theory
• Two genetic algorithms for the bandwidth multicoloring problem
• Zero knowledge and the chromatic number

Cited in

(4)

• A Simple 2-Approximation for Maximum-Leaf Spanning Tree
• Algorithms for bandwidth consecutive multicolorings of graphs (extended abstract)
• Approximation algorithms for bandwidth consecutive multicolorings (extended abstract)
• Bandwidth consecutive multicolorings of graphs

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

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