Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs

DOI10.1007/978-3-319-44543-4_27zbMath1478.68215OpenAlexW2565352292MaRDI QIDQ2819518

Robert Benkoczi, Ram Dahal, Daya Ram Gaur

Publication date: 29 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-44543-4_27

zbMATH Keywords

schedulingdynamic programmingvertex coloringbinary treescactus graphmax coloringweighted coloringspine tree decomposition

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Uses Software

• gCol

Cites Work

• Unnamed Item
• Unnamed Item
• A coloring problem for weighted graphs
• Max-coloring paths: tight bounds and extensions
• Models and heuristic algorithms for a weighted vertex coloring problem
• Weighted coloring: further complexity and approximability results
• Algorithmic complexity of list colorings
• An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment
• Batch Coloring Flat Graphs and Thin
• Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment
• Channel assignment and weighted coloring
• Weighted Coloring in Trees
• Automata, Languages and Programming

This page was built for publication: Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs