Probabilistic graph-coloring in bipartite and split graphs
type: Item
instance of: scholarly article
title: Probabilistic graph-coloring in bipartite and split graphs
zbMATH Open document ID: 1206.05039
published in: Journal of Combinatorial Optimization
publication date: 2009-10-09T00:00:00Z
full work available at URL: https://basepub.dauphine.fr/handle/123456789/2110
review text: The authors consider probabilistic coloring problems. In bipartite graphs some polynomially solvable cases are considered and some approximation results are given, using the standard- and the differential-approximation ratio. The authors show that probabilistic coloring is NP-hard in split graphs and that the existence of a fully polynomial time standard-approximation schema is impossible. However, they provide a polynomial time standard-approximation schema under any system of vertex-probabilities and a polynomial time differential-approximation schema under identical vertex-probabilities.
reviewed by: Svetlana A. Kravchenko
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5612785
zbMATH Keywords: probabilistic optimization
zbMATH Keywords: approximation algorithms
zbMATH Keywords: graph coloring
author: Nicolas Bourgeois
author: F. Della Croce
author: Bruno Escoffier
author: C. Murat
author: Vangelis Th. Paschos
MaRDI profile type: Publication
OpenAlex ID: W2070627531
cites work: Probabilistic a priori routing-location problems
cites work: Probabilistic combinatorial optimization problems on graphs: A new domain in operational research
cites work: Q5668821
cites work: Traveling Salesman Facility Location Problems
cites work: The probabilistic minimum spanning tree problem
cites work: A Priori Optimization
cites work: Local search for the probabilistic traveling salesman problem: correction to the 2-p-opt and 1-shift algorithms
cites work: Scheduling with incompatible jobs
cites work: Node-weighted graphs having the König-Egerváry property
cites work: Approximation results for the minimum graph coloring problem
cites work: Differential approximation algorithms for some combinatorial optimization problems
cites work: Q4198056
cites work: Q4886045
cites work: \(z\)-approximations
cites work: Q3677509
cites work: A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited
cites work: Shortest path problems with node failures
cites work: Q3799802
cites work: Approximation algorithms for combinatorial problems
cites work: The probabilistic longest path problem
cites work: A priori optimization for the probabilistic maximum independent set problem
cites work: The Probabilistic Minimum Vertex-covering Problem
cites work: On the probabilistic minimum coloring and minimum \(k\)-coloring
cites work: On Approximate Solutions for Combinatorial Optimization Problems
DOI: 10.1007/S10878-007-9112-2
description: scientific article; zbMATH DE number 5612785