Open Access
Open access
Springer Nature
Lecture Notes in Computer Science
,  страницы 125-136

A Work-Optimal Coarse-Grained PRAM Algorithm for Lexicographically First Maximal Independent Set

Тип публикации: Book Chapter
Дата публикации: 2003-01-01
Springer Nature
scimago Q2
SJR: 0.352
CiteScore: 2.4
Impact factor: —
ISSN: 03029743, 16113349, 18612075, 18612083
Краткое описание
The Lexicographically First Maximal Independent Set Problem on graphs with bounded degree 3 is at most $\sqrt{n}$ -complete, and thus very likely not parallelizable in a fine-grained setting. On the other hand, we show that in a coarse-grained setting (few processors and a lot of data) the situation is different, by giving a work-optimal algorithm on a shared memory machine for n and p such that p ·log p  ∈ O(log n).

Вы ученый?

Создайте профиль, чтобы получать персональные рекомендации коллег, конференций и новых статей.
 Войти с ORCID
Метрики
0
Поделиться
Цитировать
ГОСТ |
Цитировать
ГОСТ Скопировать
GUSTEDT J., TELLE J. A. A Work-Optimal Coarse-Grained PRAM Algorithm for Lexicographically First Maximal Independent Set // Lecture Notes in Computer Science. 2003. pp. 125-136.
ГОСТ со всеми авторами (до 50) Скопировать
GUSTEDT J., TELLE J. A. A Work-Optimal Coarse-Grained PRAM Algorithm for Lexicographically First Maximal Independent Set // Lecture Notes in Computer Science. 2003. pp. 125-136.
RIS |
Цитировать
RIS Скопировать
TY - GENERIC
DO - 10.1007/978-3-540-45208-9_11
UR - https://doi.org/10.1007/978-3-540-45208-9_11
TI - A Work-Optimal Coarse-Grained PRAM Algorithm for Lexicographically First Maximal Independent Set
T2 - Lecture Notes in Computer Science
AU - GUSTEDT, JENS
AU - TELLE, JAN ARNE
PY - 2003
DA - 2003/01/01
PB - Springer Nature
SP - 125-136
SN - 0302-9743
SN - 1611-3349
SN - 1861-2075
SN - 1861-2083
ER -
BibTex
Цитировать
BibTex (до 50 авторов) Скопировать
@incollection{2003_GUSTEDT,
author = {JENS GUSTEDT and JAN ARNE TELLE},
title = {A Work-Optimal Coarse-Grained PRAM Algorithm for Lexicographically First Maximal Independent Set},
publisher = {Springer Nature},
year = {2003},
pages = {125--136},
month = {jan}
}
Ошибка в публикации?