Online algorithms for the maximum \(k\)-colorable subgraph problem

DOI10.1016/j.cor.2017.10.003zbMath1391.05244OpenAlexW2761361573MaRDI QIDQ1652561

François Gagnon, Alain Hertz, Romain Montagné

Publication date: 11 July 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2017.10.003

zbMATH Keywords

competitive analysisonline algorithmsmaximum \(k\)-colorable subgraphsequential vertex coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items

The Maximum k-Colorable Subgraph Problem and Related Problems, An online algorithm for the inventory retrieval problem with an uncertain selling duration, uncertain prices, and price-dependent demands, Online optimisation for ambulance routing in disaster response with partial or no information on victim conditions

Uses Software

• Tabu search

Cites Work

• Using tabu search techniques for graph coloring
• The maximum \(k\)-colorable subgraph problem and orbitopes
• An on-line graph coloring algorithm with sublinear performance ratio
• The node-deletion problem for hereditary properties is NP-complete
• The smallest hard-to-color graph
• Future paths for integer programming and links to artificial intelligence
• Constructive algorithms for the partial directed weighted improper coloring problem
• A general approach to online network optimization problems
• Online Dual Edge Coloring of Paths and Trees
• Weighted Bipartite Matching in Matrix Multiplication Time
• On-line and first fit colorings of graphs
• A graph coloring algorithm for large scheduling problems
• New methods to color the vertices of a graph
• The approximation of maximum subgraph problems
• On the recursive largest first algorithm for graph colouring
• An upper bound for the chromatic number of a graph and its application to timetabling problems