Algorithms for Coloring Semi-random Graphs

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

Local TagsRelease HistoryDetailsSummary

Algorithms for Coloring Semi-random Graphs

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

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-374A-9 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-374B-7

Genre: Journal Article

Files

show Files

Locators

show

Creators

show

hide

Creators:
Subramanian, C. R.¹, Author
Fürer, Martin¹, Author
Veni Madhavan, C. E.², Author

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019
2Max Planck Society, ou_persistent13

Content

show

hide

Free keywords: -

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.

Details

show

hide

Language(s): eng - English

Dates: Modified: 2010-03-02Date issued: 1998

Publication Status: Issued

Pages: -

Publishing info: -

Table of Contents: -

Rev. Type: Peer

Identifiers: eDoc: 517990
Other: Local-ID: C1256428004B93B8-F7A3B6132B5F468AC1256716006084EF-CRS98b

Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show

hide

Title: Random Structures & Algorithms

Source Genre: Journal

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: 13 (2) Sequence Number: - Start / End Page: 125 - 158 Identifier: ISSN: 1042-9832