Datové struktury a časová složitost algoritmů

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Data Structures and Time Complexity of Algorithms

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Data Structures and Time Complexity of Algorithms

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BB - Aplikovaná statistika, operační výzkum

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2005

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 4th International Conference Aplimat

ISBN

80-969264-2-X

ISSN

—

e-ISSN

—

Počet stran výsledku

6

Strana od-do

245-250

Název nakladatele

Slovak University of Technology

Místo vydání

Bratislava (Slovakia)

Místo konání akce

Bratislava

Datum konání akce

1. 2. 2005

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—