This HTML5 document contains 40 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n12http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
dctermshttp://purl.org/dc/terms/
n15http://purl.org/net/nknouf/ns/bibtex#
n6http://localhost/temp/predkladatel/
n21http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n14http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216305%3A26210%2F08%3APU76870%21RIV10-MSM-26210___/
n8http://linked.opendata.cz/ontology/domain/vavai/
n17https://schema.org/
n9http://linked.opendata.cz/resource/domain/vavai/zamer/
shttp://schema.org/
n4http://linked.opendata.cz/ontology/domain/vavai/riv/
skoshttp://www.w3.org/2004/02/skos/core#
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n5http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n16http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n20http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n7http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n19http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n10http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n18http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216305%3A26210%2F08%3APU76870%21RIV10-MSM-26210___
rdf:type
n8:Vysledek skos:Concept
dcterms:description
The Euclidean Steiner Tree Problem is to find a shortest network spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set. The problem being NP-hard, polynomial-time approximations or heuristics are required. There are many rather complex heuristics based, e.g., on enumerating full topologies and consuming long time for computations for large instances. In this paper, we applied to use tools of computational geometry, especially the properties of Delaunay triangulation, a well-known geometric structure, and combine them with insertion heuristics based on the construction of the Euclidean minimum spanning tree. Thus an algorithm could be proposed that is very efficient and fast. Experiments confirmed that computations by this algorithm generate very good results in a reasonable amount of time, even for large instances of the studied problem. The Euclidean Steiner Tree Problem is to find a shortest network spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set. The problem being NP-hard, polynomial-time approximations or heuristics are required. There are many rather complex heuristics based, e.g., on enumerating full topologies and consuming long time for computations for large instances. In this paper, we applied to use tools of computational geometry, especially the properties of Delaunay triangulation, a well-known geometric structure, and combine them with insertion heuristics based on the construction of the Euclidean minimum spanning tree. Thus an algorithm could be proposed that is very efficient and fast. Experiments confirmed that computations by this algorithm generate very good results in a reasonable amount of time, even for large instances of the studied problem.
dcterms:title
Solving the Euclidean Steiner Tree Problem Using Geometric Structures Solving the Euclidean Steiner Tree Problem Using Geometric Structures
skos:prefLabel
Solving the Euclidean Steiner Tree Problem Using Geometric Structures Solving the Euclidean Steiner Tree Problem Using Geometric Structures
skos:notation
RIV/00216305:26210/08:PU76870!RIV10-MSM-26210___
n4:aktivita
n20:Z
n4:aktivity
Z(MSM0021630529)
n4:dodaniDat
n18:2010
n4:domaciTvurceVysledku
n21:1920863
n4:druhVysledku
n10:D
n4:duvernostUdaju
n16:S
n4:entitaPredkladatele
n14:predkladatel
n4:idSjednocenehoVysledku
395865
n4:idVysledku
RIV/00216305:26210/08:PU76870
n4:jazykVysledku
n7:eng
n4:klicovaSlova
Steiner tree, Steiner ratio, heuristic, Delaunay triangulation
n4:klicoveSlovo
n5:Delaunay%20triangulation n5:heuristic n5:Steiner%20tree n5:Steiner%20ratio
n4:kontrolniKodProRIV
[A3EF6DBDB1E3]
n4:mistoKonaniAkce
Brno University of Technology
n4:mistoVydani
Brno
n4:nazevZdroje
Proceedings of the 14th International Conference on Soft Computing MENDEL 2008
n4:obor
n19:BB
n4:pocetDomacichTvurcuVysledku
1
n4:pocetTvurcuVysledku
1
n4:rokUplatneniVysledku
n18:2008
n4:tvurceVysledku
Šeda, Miloš
n4:typAkce
n12:WRD
n4:zahajeniAkce
2008-06-18+02:00
n4:zamer
n9:MSM0021630529
s:numberOfPages
8
n15:hasPublisher
Vysoké učení technické v Brně. Fakulta strojního inženýrství
n17:isbn
978-80-214-3675-6
n6:organizacniJednotka
26210