Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Subramanian, C. R.

dblp



BibTeX cite key*:

crsjalg

Title

Title*:

Minimum Coloring k-Colorable Graphs in Polynomial Average Time

Journal

Journal Title*:

Journal of Algorithms

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Academic Press

Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

33

Number:


Publishing Date:

October 1999

Pages*:

112-123

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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.

URL for the Abstract:


Categories,
Keywords:

graph coloring, random graphs, polynomial average time.

HyperLinks / References / URLs:

http://www.idealibrary.com

Copyright Message:


Personal Comments:


Download
Access Level:


Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat


BibTeX Entry:

@ARTICLE{crsjalg,
AUTHOR = {Subramanian, C. R.},
TITLE = {Minimum Coloring k-Colorable Graphs in Polynomial Average Time},
JOURNAL = {Journal of Algorithms},
PUBLISHER = {Academic Press},
YEAR = {1999},
VOLUME = {33},
PAGES = {112--123},
MONTH = {October},
}


Entry last modified by Uwe Brahm, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
C. R. Subramanian
Created
03/24/2000 04:12:45 PM
Revision
1.
0.


Editor
Uwe Brahm
C. R. Subramanian


Edit Date
04.04.2000 12:03:26
24/03/2000 16:12:46