Graph and Geometric Algorithms and Efficient Data Structures
The result's identifiers
Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Graph and Geometric Algorithms and Efficient Data Structures
Original language description
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
Czech name
—
Czech description
—
Classification
Type
C - Chapter in a specialist book
CEP classification
BB - Applied statistics, operational research
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA102%2F09%2F1680" target="_blank" >GA102/09/1680: Control Algorithm Design by Means of Evolutionary Approach</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2012
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
Book/collection name
Zelinka, I., Snášel, V., Abraham, A. (eds.): Handbook of Optimization. From Classical to Modern Approach.
ISBN
978-3-642-30503-0
Number of pages of the result
23
Pages from-to
73-95
Number of pages of the book
1100
Publisher name
Springer-Verlag
Place of publication
Berlin (Germany)
UT code for WoS chapter
—