The Library
New streaming algorithms for parameterized maximal matching & beyond
Tools
Tools
Tools
Chitnis, Rajesh, Cormode, Graham, Esfandiari, Hossein, Hajiaghayi, Mohammad Taghi and Monemizadeh, Morteza (2015) New streaming algorithms for parameterized maximal matching & beyond. In: 27th ACM symposium on Parallelism in Algorithms and Architectures, Portland, Oregon, USA, 13-15 Jun 2015. Published in: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures pp. 56-58. ISBN 9781450335881. doi:10.1145/2755573.2755618
|
PDF
WRAP_maxmatching.pdf - Accepted Version - Requires a PDF viewer. Download (448Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/2755573.2755618
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].
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science > Computer Science | ||||
| Journal or Publication Title: | Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures | ||||
| Publisher: | ACM | ||||
| ISBN: | 9781450335881 | ||||
| Official Date: | 2015 | ||||
| Dates: |
|
||||
| Date of first compliant deposit: | 3 March 2016 | ||||
| Date of first compliant Open Access: | 3 March 2016 | ||||
| Page Range: | pp. 56-58 | ||||
| DOI: | 10.1145/2755573.2755618 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Funder: | Israeli Centers of Research Excellence (I-CORE), Yahoo! Research Labs, Royal Society (Great Britain). Wolfson Research Merit Award (RSWRMA), National Science Foundation (U.S.) (NSF), United States. Office of Naval Research, United States. Defense Advanced Research Projects Agency (DARPA), United States. Air Force. Office of Scientific Research (AFOSR), Google (Firm), Czech Science Foundation (CSF) | ||||
| Grant number: | 1053605 (NSF), CCF-1161626 (NSF),N000141110662 (ONR), FA9550-12-1-0423 (DAPRA), 14-10003S (CSF) | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | 27th ACM symposium on Parallelism in Algorithms and Architectures | ||||
| Type of Event: | Conference | ||||
| Location of Event: | Portland, Oregon, USA | ||||
| Date(s) of Event: | 13-15 Jun 2015 | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
