English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

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;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
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: http://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.