Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Zito M.A.A. — Randomized techniques in combinatorial algorithms
Zito M.A.A. — Randomized techniques in combinatorial algorithms



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Randomized techniques in combinatorial algorithms

Автор: Zito M.A.A.

Аннотация:

Probabilistic techniques are becoming more and more important in Computer Science.
Some of them are useful for the analysis of algorithms. The aim of this thesis is to describe and develop applications of these techniques.
We first look at the problem of generating a graph uniformly at random from the set of all unlabelled graphs with n vertices, by means of efficient parallel algorithms. Our model of parallel computation is the well-known parallel random access machine (PRAM). The algorithms presented here are among the first parallel algorithms for random generation of combinatorial structures. We present two different parallel algorithms for the uniform generation of unlabelled graphs. The algorithms run in O(log2 n) time with high probability on an EREW PRAM using O(n2) processors.
Finally we look at two graph theoretic matching problems. We first study the computational complexity of these problems and the algorithmic approximability of the optimal solutions, in particular classes of graphs. We also derive an algorithm that solves one of them optimally in linear time when the input graph is a tree as well as a number of non-approximability results. Then we make some assumptions about the input distribution, we study the expected structure of these matchings and we derive improved approximation results on several models of random graphs.


Язык: en

Рубрика: Computer science/Алгоритмы/

Тип: Диссертация

Статус предметного указателя: Неизвестно

ed2k: ed2k stats

Год издания: 1999

Количество страниц: 141

Добавлена в каталог: 25.11.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте