Zobrazeno 1 - 8
of 8
pro vyhledávání: '"Elena Losievskaja"'
Publikováno v:
Algorithmica. 76:490-501
We give the first treatment of the classic independent set problem in graphs and hypergraphs in the streaming setting. The objective is to find space-efficient algorithms that output independent sets that are "combinatorially optimal", that is, with
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a03d88a35bdb99fe138513c1f6955230
https://doi.org/10.1007/s00453-015-0051-5
https://doi.org/10.1007/s00453-015-0051-5
Autor:
Frances A. Rosamond, Daniel Lokshtanov, Fedor V. Fomin, Elena Losievskaja, Michael R. Fellows, Saket Saurabh
Publikováno v:
ACM Transactions on Computation Theory. 5:1-20
We study low-distortion embedding of metric spaces into the line, and more generally, into the shortest path metric of trees, from the parameterized complexity perspective. Let M = M ( G ) be the shortest path metric of an edge-weighted graph G , wit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f5dc78918c6a8b6d385d45408ffbd8e3
https://doi.org/10.1145/2489789
https://doi.org/10.1145/2489789
Publikováno v:
Theoretical Computer Science. 470:1-9
This paper deals with approximations of maximum independent sets in non-uniform hypergraphs of low degree. We obtain the first performance ratio that is sublinear in terms of the maximum or average degree of the hypergraph. We extend this to the weig
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::92788e72ceb5958388756c602fcbfae6
Publikováno v:
Discrete Applied Mathematics. 157(8):1773-1786
In this paper we analyze several approaches to the Maximum Independent Set (MIS) problem in hypergraphs with degree bounded by a parameter @D. Since independent sets in hypergraphs can be strong and weak, we denote by MIS (MSIS) the problem of findin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8fd62bd879580ea470e9943863491be5
Publikováno v:
Automata, Languages and Programming ISBN: 9783642141645
ICALP (1)
ICALP (1)
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
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::89d03fb64aea6d2b70b75139e485f289
https://doi.org/10.1007/978-3-642-14165-2_54
https://doi.org/10.1007/978-3-642-14165-2_54
Publikováno v:
Automata, Languages and Programming ISBN: 9783642029264
ICALP (1)
ICALP (1)
This paper deals with approximations of maximum independent sets in non-uniform hypergraphs of low degree. We obtain the first performance ratio that is sublinear in terms of the maximum or average degree of the hypergraph. We extend this to the weig
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::77d8aa8d29ec86250c8b0f6ae98aa1d3
https://doi.org/10.1007/978-3-642-02927-1_3
https://doi.org/10.1007/978-3-642-02927-1_3
Autor:
Saket Saurabh, Daniel Lokshtanov, Frances A. Rosamond, Michael R. Fellows, Elena Losievskaja, Fedor V. Fomin
Publikováno v:
Automata, Languages and Programming ISBN: 9783642029264
ICALP (1)
ICALP (1)
We study low-distortion embedding of metric spaces into the line, and more generally, into the shortest path metric of trees, from the parameterized complexity perspective. Let M = M (G ) be the shortest path metric of an edge weighted graph G , with
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a9bb7f4d9405756bd909bec44ff248b1
https://doi.org/10.1007/978-3-642-02927-1_39
https://doi.org/10.1007/978-3-642-02927-1_39
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783540739487
WADS
WADS
In this paper we analyze several approaches to the Maximum Independent Set problem in hypergraphs with degree bounded by Δ. We propose a general technique that reduces the worst case analysis of certain algorithms to their performance in the case of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3c9c0961dd9a52d4c6b66255051e939e
https://doi.org/10.1007/978-3-540-73951-7_24
https://doi.org/10.1007/978-3-540-73951-7_24