Coloring random graphs in polynomial expected time

Martin Furer; C. R. Subramanian; C. E.Veni Madhavan

doi:10.1007/3-540-57568-5_232

Coloring random graphs in polynomial expected time

Martin Furer, C. R. Subramanian, C. E.Veni Madhavan

Eberly College of Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Scopus citations

Abstract

We consider the problem of vertex coloring random k-colorable graphs using k colors. We consider two different models for generating random graphs. We give algorithms for coloring random graphs in these models, with running times polynomial on the average. The first model is discussed in Turner [6] and the second model is discussed in Dyer and Frieze [3]. Our results improve the these current results for this problem by removing the assumption ofconstant edge probability used in these models.

Original language	English (US)
Title of host publication	Algorithms and Computation - 4th International Symposium, ISAAC 1993, Proceedings
Editors	Kam Wing Ng, Prabhakar Raghavan, N.V. Balasubramanian, Francis Y.L. Chin
Publisher	Springer Verlag
Pages	31-37
Number of pages	7
ISBN (Print)	9783540575689
DOIs	https://doi.org/10.1007/3-540-57568-5_232
State	Published - 1993
Event	4th International Symposium on Algorithms and Computation, ISAAC 1993 - Hong Kong, China Duration: Dec 15 1993 → Dec 17 1993

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	762 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	4th International Symposium on Algorithms and Computation, ISAAC 1993
Country/Territory	China
City	Hong Kong
Period	12/15/93 → 12/17/93

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-57568-5_232

Cite this

Furer, M., Subramanian, C. R., & Madhavan, C. E. V. (1993). Coloring random graphs in polynomial expected time. In K. W. Ng, P. Raghavan, N. V. Balasubramanian, & F. Y. L. Chin (Eds.), Algorithms and Computation - 4th International Symposium, ISAAC 1993, Proceedings (pp. 31-37). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 762 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-57568-5_232

Furer, Martin ; Subramanian, C. R. ; Madhavan, C. E.Veni. / Coloring random graphs in polynomial expected time. Algorithms and Computation - 4th International Symposium, ISAAC 1993, Proceedings. editor / Kam Wing Ng ; Prabhakar Raghavan ; N.V. Balasubramanian ; Francis Y.L. Chin. Springer Verlag, 1993. pp. 31-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{654d810800844d5aa288e16e9b20edb7,

title = "Coloring random graphs in polynomial expected time",

abstract = "We consider the problem of vertex coloring random k-colorable graphs using k colors. We consider two different models for generating random graphs. We give algorithms for coloring random graphs in these models, with running times polynomial on the average. The first model is discussed in Turner [6] and the second model is discussed in Dyer and Frieze [3]. Our results improve the these current results for this problem by removing the assumption ofconstant edge probability used in these models.",

author = "Martin Furer and Subramanian, {C. R.} and Madhavan, {C. E.Veni}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1993.; 4th International Symposium on Algorithms and Computation, ISAAC 1993 ; Conference date: 15-12-1993 Through 17-12-1993",

year = "1993",

doi = "10.1007/3-540-57568-5_232",

language = "English (US)",

isbn = "9783540575689",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "31--37",

editor = "Ng, {Kam Wing} and Prabhakar Raghavan and N.V. Balasubramanian and Chin, {Francis Y.L.}",

booktitle = "Algorithms and Computation - 4th International Symposium, ISAAC 1993, Proceedings",

address = "Germany",

}

Furer, M, Subramanian, CR & Madhavan, CEV 1993, Coloring random graphs in polynomial expected time. in KW Ng, P Raghavan, NV Balasubramanian & FYL Chin (eds), Algorithms and Computation - 4th International Symposium, ISAAC 1993, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 762 LNCS, Springer Verlag, pp. 31-37, 4th International Symposium on Algorithms and Computation, ISAAC 1993, Hong Kong, China, 12/15/93. https://doi.org/10.1007/3-540-57568-5_232

Coloring random graphs in polynomial expected time. / Furer, Martin; Subramanian, C. R.; Madhavan, C. E.Veni.
Algorithms and Computation - 4th International Symposium, ISAAC 1993, Proceedings. ed. / Kam Wing Ng; Prabhakar Raghavan; N.V. Balasubramanian; Francis Y.L. Chin. Springer Verlag, 1993. p. 31-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 762 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Coloring random graphs in polynomial expected time

AU - Furer, Martin

AU - Subramanian, C. R.

AU - Madhavan, C. E.Veni

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1993.

PY - 1993

Y1 - 1993

N2 - We consider the problem of vertex coloring random k-colorable graphs using k colors. We consider two different models for generating random graphs. We give algorithms for coloring random graphs in these models, with running times polynomial on the average. The first model is discussed in Turner [6] and the second model is discussed in Dyer and Frieze [3]. Our results improve the these current results for this problem by removing the assumption ofconstant edge probability used in these models.

AB - We consider the problem of vertex coloring random k-colorable graphs using k colors. We consider two different models for generating random graphs. We give algorithms for coloring random graphs in these models, with running times polynomial on the average. The first model is discussed in Turner [6] and the second model is discussed in Dyer and Frieze [3]. Our results improve the these current results for this problem by removing the assumption ofconstant edge probability used in these models.

UR - http://www.scopus.com/inward/record.url?scp=84949825861&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84949825861&partnerID=8YFLogxK

U2 - 10.1007/3-540-57568-5_232

DO - 10.1007/3-540-57568-5_232

M3 - Conference contribution

AN - SCOPUS:84949825861

SN - 9783540575689

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 31

EP - 37

BT - Algorithms and Computation - 4th International Symposium, ISAAC 1993, Proceedings

A2 - Ng, Kam Wing

A2 - Raghavan, Prabhakar

A2 - Balasubramanian, N.V.

A2 - Chin, Francis Y.L.

PB - Springer Verlag

T2 - 4th International Symposium on Algorithms and Computation, ISAAC 1993

Y2 - 15 December 1993 through 17 December 1993

ER -

Furer M, Subramanian CR, Madhavan CEV. Coloring random graphs in polynomial expected time. In Ng KW, Raghavan P, Balasubramanian NV, Chin FYL, editors, Algorithms and Computation - 4th International Symposium, ISAAC 1993, Proceedings. Springer Verlag. 1993. p. 31-37. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-57568-5_232

Coloring random graphs in polynomial expected time

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this