Data Structures and Time Complexity of Algorithms
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F05%3APU53765" target="_blank" >RIV/00216305:26210/05:PU53765 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Data Structures and Time Complexity of Algorithms
Original language description
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 binnary 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.
Czech name
Datové struktury a časová složitost algoritmů
Czech description
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í hhaldu. 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ů.
Classification
Type
D - Article in proceedings
CEP classification
BB - Applied statistics, operational research
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2005
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 4th International Conference Aplimat
ISBN
80-969264-2-X
ISSN
—
e-ISSN
—
Number of pages
6
Pages from-to
245-250
Publisher name
Slovak University of Technology
Place of publication
Bratislava (Slovakia)
Event location
Bratislava
Event date
Feb 1, 2005
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—