All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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