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
![[thumbnail of WRAP_maxmatching.pdf]](https://cdn.statically.io/img/wrap.warwick.ac.uk/74442/7.hassmallThumbnailVersion/WRAP_maxmatching.pdf)  Preview |
PDF
WRAP_maxmatching.pdf - Accepted Version - Requires a PDF viewer. Download (458kB) | Preview |
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, Engineering and Medicine > 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 Event 2015 Published |
| 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 |
| Date of first compliant deposit: | 3 March 2016 |
| Date of first compliant Open Access: | 3 March 2016 |
| 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: | |
| Persistent URL: | https://wrap.warwick.ac.uk/74442/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |