𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Analysis of greedy algorithms on graphs with bounded degrees

✍ Scribed by Nicholas C. Wormald

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
370 KB
Volume
273
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We give a general result on the average-case performance of certain greedy algorithms. These are derived from algorithms in which the possible operations performed at each step are prioritised. This type of prioritisation has occurred in previously studied heuristics for ÿnding large subgraphs with special properties in random regular graphs, such as maximum independent sets and minimum dominating sets. The approach in this paper eliminates some of the complications caused by prioritisation. The main results apply in general to random graphs with a given degree sequence.

📜 SIMILAR VOLUMES

Worst case analysis of a greedy algorith
Worst case analysis of a greedy algorithm for graph thickness
✍ Sinichiro Kawano; Koichi Yamazaki 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 208 KB

In this paper, we consider a greedy algorithm for thickness of graphs. The greedy algorithm we consider here takes a maximum planar subgraph away from the current graph in each iteration and repeats this process until the current graph has no edge. The greedy algorithm outputs the number of iteratio

On Induced Ramsey Numbers for Graphs wit
On Induced Ramsey Numbers for Graphs with Bounded Maximum Degree
✍ Tomasz Łuczak; Vojtěch Rödl 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 435 KB

For graphs G and H we write G wÄ ind H if every 2-edge colouring of G yields an induced monochromatic copy of H. The induced Ramsey number for H is defined as r ind (H)=min[ |V(G)|: G wÄ ind H]. We show that for every d 1 there exists an absolute constant c d such that r ind (H n, d ) n cd for every

Degree-bounded coloring of graphs: Varia
Degree-bounded coloring of graphs: Variations on a theme by brooks
✍ S. L. Hakimi; J. Mitchem; E. F. Schmeichel 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 876 KB

## Abstract A graph __G__ is degree‐bounded‐colorable (briefly, db‐colorable) if it can be properly vertex‐colored with colors 1,2, …, k ≤ Δ(__G__) such that each vertex __v__ is assigned a color __c__(__v__) ≤ __v__. We first prove that if a connected graph __G__ has a block which is neither a com