Finding a maximum matching in a sparse random graph in O(n) expected time

Prasad Chebolu; Alan Frieze; Páll Melsted

doi:10.1007/978-3-540-70575-8_14

Finding a maximum matching in a sparse random graph in O(n) expected time

Prasad Chebolu
, Alan Frieze
, Páll Melsted

Faculty of Industrial Engineering, Mechanical Engineering and Computer Science

University of Iceland

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

Abstract

We present a linear expected time algorithm for finding maximum cardinality matchings in sparse random graphs. This is optimal and improves on previous results by a logarithmic factor.

Original language	English
Title of host publication	Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
Pages	161-172
Number of pages	12
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-540-70575-8_14
Publication status	Published - 2008
Event	35th International Colloquium on Automata, Languages and Programming, ICALP 2008 - Reykjavik, Iceland Duration: 7 Jul 2008 → 11 Jul 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	5125 LNCS

Conference

Conference	35th International Colloquium on Automata, Languages and Programming, ICALP 2008
Country/Territory	Iceland
City	Reykjavik
Period	7/07/08 → 11/07/08

Access to Document

10.1007/978-3-540-70575-8_14

Cite this

Chebolu, P., Frieze, A., & Melsted, P. (2008). Finding a maximum matching in a sparse random graph in O(n) expected time. In Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings (PART 1 ed., pp. 161-172). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5125 LNCS, No. PART 1). https://doi.org/10.1007/978-3-540-70575-8_14

Chebolu, Prasad ; Frieze, Alan ; Melsted, Páll. / Finding a maximum matching in a sparse random graph in O(n) expected time. Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 1. ed. 2008. pp. 161-172 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{712dd11e4f334d7f96c84c8daec177c5,

title = "Finding a maximum matching in a sparse random graph in O(n) expected time",

abstract = "We present a linear expected time algorithm for finding maximum cardinality matchings in sparse random graphs. This is optimal and improves on previous results by a logarithmic factor.",

author = "Prasad Chebolu and Alan Frieze and P{\'a}ll Melsted",

year = "2008",

doi = "10.1007/978-3-540-70575-8\_14",

language = "English",

isbn = "3540705740",

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

number = "PART 1",

pages = "161--172",

booktitle = "Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings",

edition = "PART 1",

note = "35th International Colloquium on Automata, Languages and Programming, ICALP 2008 ; Conference date: 07-07-2008 Through 11-07-2008",

}

Chebolu, P, Frieze, A & Melsted, P 2008, Finding a maximum matching in a sparse random graph in O(n) expected time. in Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 5125 LNCS, pp. 161-172, 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, Reykjavik, Iceland, 7/07/08. https://doi.org/10.1007/978-3-540-70575-8_14

Finding a maximum matching in a sparse random graph in O(n) expected time. / Chebolu, Prasad; Frieze, Alan; Melsted, Páll.
Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 1. ed. 2008. p. 161-172 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5125 LNCS, No. PART 1).

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

TY - GEN

T1 - Finding a maximum matching in a sparse random graph in O(n) expected time

AU - Chebolu, Prasad

AU - Frieze, Alan

AU - Melsted, Páll

PY - 2008

Y1 - 2008

N2 - We present a linear expected time algorithm for finding maximum cardinality matchings in sparse random graphs. This is optimal and improves on previous results by a logarithmic factor.

AB - We present a linear expected time algorithm for finding maximum cardinality matchings in sparse random graphs. This is optimal and improves on previous results by a logarithmic factor.

UR - https://www.scopus.com/pages/publications/49049104965

U2 - 10.1007/978-3-540-70575-8_14

DO - 10.1007/978-3-540-70575-8_14

M3 - Conference contribution

SN - 3540705740

SN - 9783540705741

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

SP - 161

EP - 172

BT - Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings

T2 - 35th International Colloquium on Automata, Languages and Programming, ICALP 2008

Y2 - 7 July 2008 through 11 July 2008

ER -

Chebolu P, Frieze A, Melsted P. Finding a maximum matching in a sparse random graph in O(n) expected time. In Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 1 ed. 2008. p. 161-172. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-540-70575-8_14

Finding a maximum matching in a sparse random graph in O(n) expected time

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this