New Streaming Algorithms for Parameterized Maximal Matching
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10316189" target="_blank" >RIV/00216208:11320/15:10316189 - isvavai.cz</a>
Result on the web
<a href="http://dl.acm.org/citation.cfm?doid=2755573.2755618" target="_blank" >http://dl.acm.org/citation.cfm?doid=2755573.2755618</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/2755573.2755618" target="_blank" >10.1145/2755573.2755618</a>
Alternative languages
Result language
angličtina
Original language name
New Streaming Algorithms for Parameterized Maximal Matching
Original language description
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].
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA14-10003S" target="_blank" >GA14-10003S: Restricted computations: Algorithms, models, complexity</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures
ISBN
978-1-4503-3588-1
ISSN
—
e-ISSN
—
Number of pages
3
Pages from-to
56-58
Publisher name
The Association for Computing Machinery
Place of publication
USA
Event location
Portland, OR, USA
Event date
Jun 13, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—