The vertex coloring problem and its generalizations

DOI10.1007/S10288-008-0071-YMaRDI QIDQ1022440zbMATH OpenOpenAlexFDO

Authors Enrico Malaguti

Publication date 22 June 2009

Published in 4OR (Search for Journal in Brave)

Full work available at URL http://amsdottorato.unibo.it/340/1/TESI_Malaguti.pdf

zbMATH Keywords

vertex coloring problemefficiency of a solutionfairness of a solutionrouting problem in telecommunication networks

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Communication networks in operations research (90B18)

Recommendations

• Some generalizations of theorems on vertex coloring
• A survey on vertex coloring problems
• A new approach to the vertex coloring problem
• An exact approach for the vertex coloring problem
• Two complexity results for the vertex coloring problem
• The complexity of generalized graph colorings
• On a theorem about vertex colorings of graphs
• The intersection of two vertex coloring problems
• The complexity of some graph colouring problems
• Parameterized complexity of vertex colouring

Cites work

• A metaheuristic approach for the vertex coloring problem
• Algorithms for the bin packing problem with conflicts
• An evolutionary approach for bandwidth multicoloring problems
• Batch processing with interval graph compatibilities between tasks
• Efficient and fair routing for mesh networks
• Heuristics and lower bounds for the bin packing problem with conflicts
• Models and heuristic algorithms for a weighted vertex coloring problem

Cited in

(13)

• A Wide Branching Strategy for the Graph Coloring Problem
• A simple branching scheme for vertex coloring problems
• Algorithms for some graph theoretical optimization problems (abstract of thesis)
• On properly ordered coloring of vertices in a vertex-weighted graph
• Exact weighted vertex coloring via branch-and-price
• Adaptive feasible and infeasible tabu search for weighted vertex coloring
• Vertex coloring of a graph for memory constrained scenarios
• A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size
• On the asymmetric representatives formulation for the vertex coloring problem
• Graph coloring-based approach for railway station design analysis and capacity determination
• Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
• Some undecidable problems involving the edge-coloring and vertex-coloring of graphs
• Multicast problems in telecommunication networks

Describes a project that uses

Uses Software

• CALMA

This page was built for publication: The vertex coloring problem and its generalizations

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