Graph and Geometric Algorithms and Efficient Data Structures

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F12%3APU102952" target="_blank" >RIV/00216305:26210/12:PU102952 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Graph and Geometric Algorithms and Efficient Data Structures

Popis výsledku v původním jazyce

Many NP-complete optimization problems may be approximately solved by stochastic or deterministic heuristic methods and it is necessary to find their efficient data representation to minimize iteration computational time. In this chapter, we will touch the Minimum Steiner Tree Problems in Graphs (or Network Steiner Tree Problem), which can be solved by heuristics based on the Minimum Spanning Tree Problem and/or the Shortest Path Problem using a binary heap that enables to implement a priority queue that substantially increases the algorithm efficiency. We will also show a Delaunay triangulation-based way of finding minimal networks connecting a set of given points in the Euclidean plane using straight lines (minimum spanning tree) and its more generalcase (Steiner minimum tree) where additional points can be considered. Finally, we will deal with visibility graphs, Voronoi diagrams and rapidly exploring trees and focus on their applications in robot motion planning, where the robot s

Název v anglickém jazyce

Graph and Geometric Algorithms and Efficient Data Structures

Popis výsledku anglicky

Many NP-complete optimization problems may be approximately solved by stochastic or deterministic heuristic methods and it is necessary to find their efficient data representation to minimize iteration computational time. In this chapter, we will touch the Minimum Steiner Tree Problems in Graphs (or Network Steiner Tree Problem), which can be solved by heuristics based on the Minimum Spanning Tree Problem and/or the Shortest Path Problem using a binary heap that enables to implement a priority queue that substantially increases the algorithm efficiency. We will also show a Delaunay triangulation-based way of finding minimal networks connecting a set of given points in the Euclidean plane using straight lines (minimum spanning tree) and its more generalcase (Steiner minimum tree) where additional points can be considered. Finally, we will deal with visibility graphs, Voronoi diagrams and rapidly exploring trees and focus on their applications in robot motion planning, where the robot s

Druh

C - Kapitola v odborné knize

CEP obor

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

OECD FORD obor

—

Projekt

<a href="/cs/project/GA102%2F09%2F1680" target="_blank" >GA102/09/1680: Evoluční návrh řídicích algoritmů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2012

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 knihy nebo sborníku

Zelinka, I., Snášel, V., Abraham, A. (eds.): Handbook of Optimization. From Classical to Modern Approach.

ISBN

978-3-642-30503-0

Počet stran výsledku

23

Strana od-do

73-95

Počet stran knihy

1100

Název nakladatele

Springer-Verlag

Místo vydání

Berlin (Germany)

Kód UT WoS kapitoly

—