A faster algorithm for finding maximum independent sets in sparse graphs

Martin Fürer

doi:10.1007/11682462_46

A faster algorithm for finding maximum independent sets in sparse graphs

Martin Fürer

Eberly College of Science

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

19 Scopus citations

Abstract

An algorithm is presented for finding a maximum independent set in a connected graph with n vertices and m edges in time O(poly(n)1.2365 ^m-n). As a consequence, we find a maximum independent set in a graph of degree 3 in time O(poly (n)1.1120ⁿ), which improves the currently best results of O(1.1254ⁿ) of Chen, Kanj and Xia.

Original language	English (US)
Title of host publication	LATIN 2006
Subtitle of host publication	Theoretical Informatics - 7th Latin American Symposium, Proceedings
Publisher	Springer Verlag
Pages	491-501
Number of pages	11
ISBN (Print)	354032755X, 9783540327554
DOIs	https://doi.org/10.1007/11682462_46
State	Published - 2006
Event	LATIN 2006: Theoretical Informatics - 7th Latin American Symposium - Valdivia, Chile Duration: Mar 20 2006 → Mar 24 2006

Publication series

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

Other

Other	LATIN 2006: Theoretical Informatics - 7th Latin American Symposium
Country/Territory	Chile
City	Valdivia
Period	3/20/06 → 3/24/06

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/11682462_46

Cite this

Fürer, M. (2006). A faster algorithm for finding maximum independent sets in sparse graphs. In LATIN 2006: Theoretical Informatics - 7th Latin American Symposium, Proceedings (pp. 491-501). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3887 LNCS). Springer Verlag. https://doi.org/10.1007/11682462_46

@inproceedings{c005a6ac81774308a0b078b27a195a9f,

title = "A faster algorithm for finding maximum independent sets in sparse graphs",

abstract = "An algorithm is presented for finding a maximum independent set in a connected graph with n vertices and m edges in time O(poly(n)1.2365 m-n). As a consequence, we find a maximum independent set in a graph of degree 3 in time O(poly (n)1.1120n), which improves the currently best results of O(1.1254n) of Chen, Kanj and Xia.",

author = "Martin F{\"u}rer",

year = "2006",

doi = "10.1007/11682462_46",

language = "English (US)",

isbn = "354032755X",

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

publisher = "Springer Verlag",

pages = "491--501",

booktitle = "LATIN 2006",

address = "Germany",

note = "LATIN 2006: Theoretical Informatics - 7th Latin American Symposium ; Conference date: 20-03-2006 Through 24-03-2006",

}

Fürer, M 2006, A faster algorithm for finding maximum independent sets in sparse graphs. in LATIN 2006: Theoretical Informatics - 7th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3887 LNCS, Springer Verlag, pp. 491-501, LATIN 2006: Theoretical Informatics - 7th Latin American Symposium, Valdivia, Chile, 3/20/06. https://doi.org/10.1007/11682462_46

A faster algorithm for finding maximum independent sets in sparse graphs. / Fürer, Martin.
LATIN 2006: Theoretical Informatics - 7th Latin American Symposium, Proceedings. Springer Verlag, 2006. p. 491-501 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3887 LNCS).

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

TY - GEN

T1 - A faster algorithm for finding maximum independent sets in sparse graphs

AU - Fürer, Martin

PY - 2006

Y1 - 2006

N2 - An algorithm is presented for finding a maximum independent set in a connected graph with n vertices and m edges in time O(poly(n)1.2365 m-n). As a consequence, we find a maximum independent set in a graph of degree 3 in time O(poly (n)1.1120n), which improves the currently best results of O(1.1254n) of Chen, Kanj and Xia.

AB - An algorithm is presented for finding a maximum independent set in a connected graph with n vertices and m edges in time O(poly(n)1.2365 m-n). As a consequence, we find a maximum independent set in a graph of degree 3 in time O(poly (n)1.1120n), which improves the currently best results of O(1.1254n) of Chen, Kanj and Xia.

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

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

U2 - 10.1007/11682462_46

DO - 10.1007/11682462_46

M3 - Conference contribution

AN - SCOPUS:33745615812

SN - 354032755X

SN - 9783540327554

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

SP - 491

EP - 501

BT - LATIN 2006

PB - Springer Verlag

T2 - LATIN 2006: Theoretical Informatics - 7th Latin American Symposium

Y2 - 20 March 2006 through 24 March 2006

ER -

A faster algorithm for finding maximum independent sets in sparse graphs

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this