Brief announcement: New streaming algorithms for parameterized maximal matching & beyond

Rajesh Chitnis; Graham Cormode; Hossein Esfandiari; Mohammadtaghi Hajiaghayi; Morteza Monemizadeh

doi:10.1145/2755573.2755618

Brief announcement: New streaming algorithms for parameterized maximal matching & beyond

Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Morteza Monemizadeh

Computer Science

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

4 Citations (Scopus)

Abstract

Very recently at SODA'15 [2], we studied maximal matching via the framework of parameterized streaming, where we sought solutions under the promise that no maximal matching exceeds k in size. In this paper, we revisit this problem and provide a much simpler algorithm for this problem. We are also able to apply the same technique to the Point Line Cover problem [3].

Original language	English
Title of host publication	SPAA 2015:
Subtitle of host publication	Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures
Publisher	Association for Computing Machinery
Pages	56-58
ISBN (Electronic)	9781450335881
DOIs	https://doi.org/10.1145/2755573.2755618
Publication status	Published - 13 Jun 2015
Event	27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015 - Portland, United States Duration: 13 Jun 2015 → 15 Jun 2015

Publication series

Name	Annual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Conference	27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015
Country/Territory	United States
City	Portland
Period	13/06/15 → 15/06/15

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture

Access to Document

10.1145/2755573.2755618

Cite this

Chitnis, R., Cormode, G., Esfandiari, H., Hajiaghayi, M., & Monemizadeh, M. (2015). Brief announcement: New streaming algorithms for parameterized maximal matching & beyond. In SPAA 2015: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures (pp. 56-58). (Annual ACM Symposium on Parallelism in Algorithms and Architectures). Association for Computing Machinery . https://doi.org/10.1145/2755573.2755618

Chitnis, Rajesh ; Cormode, Graham ; Esfandiari, Hossein et al. / Brief announcement : New streaming algorithms for parameterized maximal matching & beyond. SPAA 2015: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery , 2015. pp. 56-58 (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

@inproceedings{7b2d2d382b544e249a3ef05deaf4233e,

title = "Brief announcement: New streaming algorithms for parameterized maximal matching & beyond",

abstract = "Very recently at SODA'15 [2], we studied maximal matching via the framework of parameterized streaming, where we sought solutions under the promise that no maximal matching exceeds k in size. In this paper, we revisit this problem and provide a much simpler algorithm for this problem. We are also able to apply the same technique to the Point Line Cover problem [3].",

author = "Rajesh Chitnis and Graham Cormode and Hossein Esfandiari and Mohammadtaghi Hajiaghayi and Morteza Monemizadeh",

year = "2015",

month = jun,

day = "13",

doi = "10.1145/2755573.2755618",

language = "English",

series = "Annual ACM Symposium on Parallelism in Algorithms and Architectures",

publisher = "Association for Computing Machinery ",

pages = "56--58",

booktitle = "SPAA 2015:",

note = "27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015 ; Conference date: 13-06-2015 Through 15-06-2015",

}

Chitnis, R, Cormode, G, Esfandiari, H, Hajiaghayi, M & Monemizadeh, M 2015, Brief announcement: New streaming algorithms for parameterized maximal matching & beyond. in SPAA 2015: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. Annual ACM Symposium on Parallelism in Algorithms and Architectures, Association for Computing Machinery , pp. 56-58, 27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, United States, 13/06/15. https://doi.org/10.1145/2755573.2755618

Brief announcement: New streaming algorithms for parameterized maximal matching & beyond. / Chitnis, Rajesh; Cormode, Graham; Esfandiari, Hossein et al.
SPAA 2015: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery , 2015. p. 56-58 (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

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

TY - GEN

T1 - Brief announcement

T2 - 27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015

AU - Chitnis, Rajesh

AU - Cormode, Graham

AU - Esfandiari, Hossein

AU - Hajiaghayi, Mohammadtaghi

AU - Monemizadeh, Morteza

PY - 2015/6/13

Y1 - 2015/6/13

N2 - Very recently at SODA'15 [2], we studied maximal matching via the framework of parameterized streaming, where we sought solutions under the promise that no maximal matching exceeds k in size. In this paper, we revisit this problem and provide a much simpler algorithm for this problem. We are also able to apply the same technique to the Point Line Cover problem [3].

AB - Very recently at SODA'15 [2], we studied maximal matching via the framework of parameterized streaming, where we sought solutions under the promise that no maximal matching exceeds k in size. In this paper, we revisit this problem and provide a much simpler algorithm for this problem. We are also able to apply the same technique to the Point Line Cover problem [3].

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

U2 - 10.1145/2755573.2755618

DO - 10.1145/2755573.2755618

M3 - Conference contribution

AN - SCOPUS:84950240326

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 56

EP - 58

BT - SPAA 2015:

PB - Association for Computing Machinery

Y2 - 13 June 2015 through 15 June 2015

ER -

Chitnis R, Cormode G, Esfandiari H, Hajiaghayi M, Monemizadeh M. Brief announcement: New streaming algorithms for parameterized maximal matching & beyond. In SPAA 2015: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery . 2015. p. 56-58. (Annual ACM Symposium on Parallelism in Algorithms and Architectures). doi: 10.1145/2755573.2755618

Brief announcement: New streaming algorithms for parameterized maximal matching & beyond

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this