Algorithms for Coloring Semi-random Graphs

Subramanian, C. R.; Fürer, Martin; Veni Madhavan, C. E.

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

Algorithms for Coloring Semi-random Graphs

MPS-Authors

/persons/resource/persons45571

Subramanian, C. R.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44460

Fürer, Martin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Veni Madhavan, C. E.
Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Subramanian, C. R., Fürer, M., & Veni Madhavan, C. E. (1998). Algorithms for Coloring Semi-random Graphs. Random Structures & Algorithms, 13(2), 125-158.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-374A-9

Abstract

Polynomial average time algorithms for $k$-coloring semi-random $k$-colorable graphs are presented and analyzed. Semi-random graphs are a generalization of random graphs and in terms of randomness, this model lies between random graphs and worst-case model.