Streaming algorithms for independent sets

Bjarni V. Halldórsson; Magnús M. Halldórsson; Elena Losievskaja; Mario Szegedy

doi:10.1007/978-3-642-14165-2_54

Streaming algorithms for independent sets

Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, Mario Szegedy

School of Arts and Sciences, Computer Science

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

17 Scopus citations

Abstract

We find "combinatorially optimal" (guaranteed by the degree-sequence alone) independent sets for graphs and hypergraps in linear space in the semi-streaming model. We also propose a new output-efficient streaming model, that is more restrictive than semi-streaming (n •log ^O(1) n space) but more flexible than classic streaming (log ^O(1) n space). The algorithms in this model work in poly-logarithmic space, like in the case of the classical streaming model, but they can access and update the output buffer, treating it as an extra piece of memory. Our results form the first treatment of the classic IS problem in the streaming setting.

Original language	English (US)
Title of host publication	Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings
Pages	641-652
Number of pages	12
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-14165-2_54
State	Published - 2010
Event	37th International Colloquium on Automata, Languages and Programming, ICALP 2010 - Bordeaux, France Duration: Jul 6 2010 → Jul 10 2010

Publication series

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

Other

Other	37th International Colloquium on Automata, Languages and Programming, ICALP 2010
Country/Territory	France
City	Bordeaux
Period	7/6/10 → 7/10/10

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-14165-2_54

Cite this

Halldórsson, B. V., Halldórsson, M. M., Losievskaja, E., & Szegedy, M. (2010). Streaming algorithms for independent sets. In Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings (PART 1 ed., pp. 641-652). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6198 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-14165-2_54

Halldórsson, Bjarni V. ; Halldórsson, Magnús M. ; Losievskaja, Elena et al. / Streaming algorithms for independent sets. Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1. ed. 2010. pp. 641-652 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{fdf0fb31331041b0b1af09e3bbe6428d,

title = "Streaming algorithms for independent sets",

abstract = "We find {"}combinatorially optimal{"} (guaranteed by the degree-sequence alone) independent sets for graphs and hypergraps in linear space in the semi-streaming model. We also propose a new output-efficient streaming model, that is more restrictive than semi-streaming (n •log O(1) n space) but more flexible than classic streaming (log O(1) n space). The algorithms in this model work in poly-logarithmic space, like in the case of the classical streaming model, but they can access and update the output buffer, treating it as an extra piece of memory. Our results form the first treatment of the classic IS problem in the streaming setting.",

author = "Halld{\'o}rsson, {Bjarni V.} and Halld{\'o}rsson, {Magn{\'u}s M.} and Elena Losievskaja and Mario Szegedy",

year = "2010",

doi = "10.1007/978-3-642-14165-2_54",

language = "English (US)",

isbn = "3642141641",

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

number = "PART 1",

pages = "641--652",

booktitle = "Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings",

edition = "PART 1",

note = "37th International Colloquium on Automata, Languages and Programming, ICALP 2010 ; Conference date: 06-07-2010 Through 10-07-2010",

}

Halldórsson, BV, Halldórsson, MM, Losievskaja, E & Szegedy, M 2010, Streaming algorithms for independent sets. in Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, 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. 6198 LNCS, pp. 641-652, 37th International Colloquium on Automata, Languages and Programming, ICALP 2010, Bordeaux, France, 7/6/10. https://doi.org/10.1007/978-3-642-14165-2_54

Streaming algorithms for independent sets. / Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Losievskaja, Elena et al.
Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1. ed. 2010. p. 641-652 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6198 LNCS, No. PART 1).

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

TY - GEN

T1 - Streaming algorithms for independent sets

AU - Halldórsson, Bjarni V.

AU - Halldórsson, Magnús M.

AU - Losievskaja, Elena

AU - Szegedy, Mario

PY - 2010

Y1 - 2010

N2 - We find "combinatorially optimal" (guaranteed by the degree-sequence alone) independent sets for graphs and hypergraps in linear space in the semi-streaming model. We also propose a new output-efficient streaming model, that is more restrictive than semi-streaming (n •log O(1) n space) but more flexible than classic streaming (log O(1) n space). The algorithms in this model work in poly-logarithmic space, like in the case of the classical streaming model, but they can access and update the output buffer, treating it as an extra piece of memory. Our results form the first treatment of the classic IS problem in the streaming setting.

AB - We find "combinatorially optimal" (guaranteed by the degree-sequence alone) independent sets for graphs and hypergraps in linear space in the semi-streaming model. We also propose a new output-efficient streaming model, that is more restrictive than semi-streaming (n •log O(1) n space) but more flexible than classic streaming (log O(1) n space). The algorithms in this model work in poly-logarithmic space, like in the case of the classical streaming model, but they can access and update the output buffer, treating it as an extra piece of memory. Our results form the first treatment of the classic IS problem in the streaming setting.

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

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

U2 - 10.1007/978-3-642-14165-2_54

DO - 10.1007/978-3-642-14165-2_54

M3 - Conference contribution

AN - SCOPUS:77955336137

SN - 3642141641

SN - 9783642141645

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

SP - 641

EP - 652

BT - Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings

T2 - 37th International Colloquium on Automata, Languages and Programming, ICALP 2010

Y2 - 6 July 2010 through 10 July 2010

ER -

Halldórsson BV, Halldórsson MM, Losievskaja E, Szegedy M. Streaming algorithms for independent sets. In Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1 ed. 2010. p. 641-652. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-14165-2_54

Streaming algorithms for independent sets

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this