Detail publikace
Datové struktury a časová složitost algoritmů
ŠEDA, M.
Český název
Datové struktury a časová složitost algoritmů
Anglický název
Data Structures and Time Complexity of Algorithms
Typ
článek ve sborníku ve WoS nebo Scopus
Jazyk
en
Originální abstrakt
The focus of programming techniques for solving problems of operations research, graph theory, and many others areas is on how to design good algorithms and how to analyse their efficiency. Besides the fact that many problems can be solved more or less efficiently by various algorithms, their implementation efficiency can also be controlled by used data structures. In this paper, we present a simple algorithm for solving the minimum spanning tree problem and its more efficient implementation using a binary heap. This procedure is also used for an approximation algorithm of solving the network Steiner tree problem that belongs to the class of NP-hard problems.
Český abstrakt
Středem pozornosti programovacích technik určených k řešení problémů operačního výzkumu, teorie grafů a mnoha dalších oblastí je, jak navrhnout vhodné algoritmy a jak analyzovat jejich efektivitu. Vedle skutečnosti, že mnohé problémy lze řešit více či méně efektivně různými algoritmy, jejich efektivitu lze rovněž ovlivnit použitými datovými strukturami. V příspěvku prezentujeme jednoduchý algoritmus pro řešení problému hledání minimální kostry grafu a jeho efektivnější implementaci využívající binární haldu. Tento algoritmus je dále použit jako aproximace pro řešení Steinerova problému v grafech, který patří do třídy NP-těžkých problémů.
Anglický abstrakt
The focus of programming techniques for solving problems of operations research, graph theory, and many others areas is on how to design good algorithms and how to analyse their efficiency. Besides the fact that many problems can be solved more or less efficiently by various algorithms, their implementation efficiency can also be controlled by used data structures. In this paper, we present a simple algorithm for solving the minimum spanning tree problem and its more efficient implementation using a binary heap. This procedure is also used for an approximation algorithm of solving the network Steiner tree problem that belongs to the class of NP-hard problems.
Klíčová slova anglicky
priority queue, binary heap, spanning tree, Steiner tree
Rok RIV
2005
Vydáno
01.02.2005
Nakladatel
Slovak University of Technology
Místo
Bratislava (Slovakia)
ISBN
80-969264-2-X
Kniha
Proceedings of the 4th International Conference Aplimat
Počet stran
6
BIBTEX
@inproceedings{BUT15919,
author="Miloš {Šeda},
title="Data Structures and Time Complexity of Algorithms",
booktitle="Proceedings of the 4th International Conference Aplimat",
year="2005",
month="February",
publisher="Slovak University of Technology",
address="Bratislava (Slovakia)",
isbn="80-969264-2-X"
}