Minimum Coloring k-Colorable Graphs in Polynomial Average Time

Subramanian, C. R.

Local TagsRelease HistoryDetailsSummary

Minimum Coloring k-Colorable Graphs in Polynomial Average Time

Subramanian, C. R. (1999). Minimum Coloring k-Colorable Graphs in Polynomial Average Time. Journal of Algorithms, 33, 112-123.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-35DD-D Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-35DE-B

Genre: Journal Article

Files

show Files

Locators

show

Creators

show

hide

Creators:
Subramanian, C. R.¹, Author

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

Content

show

hide

Free keywords: -

Abstract: We present algorithms for minimum coloring k-colorable graphs drawn from random and semi-random models. In the first model, each allowed edge is included with indpendent probability p. In the second model, an adversary is given the power to vary the edge probability as the random instance is built. Semi-random models were introduced as a way of striking a balance between random graphs and worst-case adversaries. Our algorithms run in polynomial time on the average. Minimum coloring is harder than k-coloring because even a ''short certificate'' is not presently known for the optimality of a coloring.

Details

show

hide

Language(s): eng - English

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

Publication Status: Issued

Pages: -

Publishing info: -

Table of Contents: -

Rev. Type: Peer

Identifiers: eDoc: 518059
Other: Local-ID: C1256428004B93B8-B680BC80F5D56F99C12568AC005390EF-crsjalg

Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show

hide

Title: Journal of Algorithms

Source Genre: Journal

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: 33 Sequence Number: - Start / End Page: 112 - 123 Identifier: -