Probabilistic graph-coloring in bipartite and split graphs

DOI10.1007/s10878-007-9112-2zbMath1206.05039OpenAlexW2070627531MaRDI QIDQ732320

Bruno Escoffier, Nicolas Bourgeois, Cécile Murat, Frederico Della Croce, Vangelis Th. Paschos

Publication date: 9 October 2009

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/2110

zbMATH Keywords

graph coloringapproximation algorithmsprobabilistic optimization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (6)

A survey on combinatorial optimization in dynamic environments ⋮ The probabilistic minimum dominating set problem ⋮ On the probabilistic min spanning tree problem ⋮ Clique partitioning of interval graphs with submodular costs on the cliques ⋮ Vertex-Uncertainty in Graph-Problems ⋮ Clique partitioning with value-monotone submodular cost

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local search for the probabilistic traveling salesman problem: correction to the 2-p-opt and 1-shift algorithms
• Approximation algorithms for combinatorial problems
• Differential approximation algorithms for some combinatorial optimization problems
• Approximation results for the minimum graph coloring problem
• Scheduling with incompatible jobs
• Probabilistic combinatorial optimization problems on graphs: A new domain in operational research
• On the probabilistic minimum coloring and minimum \(k\)-coloring
• z-Approximations
• Node-weighted graphs having the König-Egerváry property
• On Approximate Solutions for Combinatorial Optimization Problems
• The probabilistic minimum spanning tree problem
• A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited
• Shortest path problems with node failures
• The probabilistic longest path problem
• Probabilistic a priori routing-location problems
• The Probabilistic Minimum Vertex-covering Problem
• Traveling Salesman Facility Location Problems
• A Priori Optimization
• A priori optimization for the probabilistic maximum independent set problem

This page was built for publication: Probabilistic graph-coloring in bipartite and split graphs