𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Algorithms for coloring semi-random graphs

✍ Scribed by C. R. Subramanian; Martin Fürer; C. E. Veni Madhavan

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
373 KB
Volume
13
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require ␦ Ž . Ž . n ␦ ) 0 colors even for bounded chromatic k-colorable for fixed k n-vertex graphs. The situation changes dramatically if we look at the average performance of an algorithm rather than its worst case performance. A k-colorable graph drawn from certain classes of distributions can be k-colored almost surely in polynomial time. It is also possible to k-color such random graphs in polynomial average time. In this paper, we present polynomial time algorithms for k-coloring graphs drawn from the semirandom model. In this model,

📜 SIMILAR VOLUMES

Algorithmic theory of random graphs
Algorithmic theory of random graphs
✍ Alan Frieze; Colin McDiarmid 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB 👁 2 views

The theory of random graphs has been mainly concerned with structural w x properties, in particular the most likely values of various graph invariantsᎏsee Bollobas 21 . There has been increasing interest in using random graphs as models for the average case analysis of graph algorithms. In this pap

Improved bounds and algorithms for hyper
Improved bounds and algorithms for hypergraph 2-coloring
✍ Jaikumar Radhakrishnan; Aravind Srinivasan 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 259 KB 👁 1 views

We show that for all large n, every n-uniform hypergraph with at most 0 7 n/ ln n × 2 n edges can be 2-colored. This makes progress on a problem of Erdős [Nordisk Mat. Tidskrift 11, 5-10 (1963)], improving the previous-best bound of n 1/3-o 1 × 2 n due to Beck [Discrete Math. 24, 127-137 (1978)]. We

Parallel algorithms for semi-lagrangian
Parallel algorithms for semi-lagrangian advection
✍ A. V. Malevsky; S. J. Thomas 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 220 KB 👁 2 views

Numerical time step limitations associated with the explicit treatment of advection-dominated problems in computational ¯uid dynamics are often relaxed by employing Eulerian±Lagrangian methods. These are also known as semi-Lagrangian methods in the atmospheric sciences. Such methods involve backward

An algorithm for drawing planar graphs
An algorithm for drawing planar graphs
✍ Bor Plestenjak 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 382 KB 👁 1 views

A simple algorithm for drawing 3-connected planar graphs is presented. It is derived from the Fruchterman and Reingold spring embedding algorithm by deleting all repulsive forces and fixing vertices of an outer face. The algorithm is implemented in the system for manipulating discrete mathematical s

Semi-coarsening AMLI algorithms for elas
Semi-coarsening AMLI algorithms for elasticity problems
✍ Svetozar D. Margenov 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 83 KB 👁 1 views

The constant γ in the strengthened Cauchy-Buniakowski-Schwarc (CBS) inequality plays a key role in the convergence analysis of the multilevel iterative methods. We consider in this paper the approximation of the two-dimensional elasticity problem by bilinear rectangle finite elements. Two semi-coars