liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.ORCID-id: 0000-0003-1836-4200
Linköpings universitet, Institutionen för datavetenskap, Artificiell intelligens och integrerade datorsystem. Linköpings universitet, Tekniska högskolan.
Linköpings universitet, Institutionen för datavetenskap, Artificiell intelligens och integrerade datorsystem. Linköpings universitet, Tekniska högskolan.ORCID-id: 0000-0002-5500-8494
2014 (engelsk)Inngår i: Examining Robustness and Vulnerability of Networked Systems / [ed] Butenko, S., Pasiliao, E.L., Shylo, V., IOS Press, 2014, s. 26-50Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

We consider the directed Steiner tree problem (DSTP) with a constraint on the total number of arcs (hops) in the tree. This problem is known to be NP-hard, and therefore, only heuristics can be applied in the case of its large-scale instances.For the hop-constrained DSTP, we propose local search strategies aimed at improving any heuristically produced initial Steiner tree. They are based on solving a sequence of hop-constrained shortest path problems for which we have recently developed efficient label correcting algorithms.The presented approach is applied to finding suitable 3D locations where unmanned aerial vehicles (UAVs) can be placed to relay information gathered in multi-target monitoring and surveillance. The efficiency of our algorithms is illustrated by results of numerical experiments involving problem instances with up to 40 000 nodes and up to 20 million arcs.

sted, utgiver, år, opplag, sider
IOS Press, 2014. s. 26-50
Serie
NATO Science for Peace and Security Series - D: Information and Communication Security, ISSN 1874-6268, E-ISSN 1879-8292 ; 37
Emneord [en]
Steiner trees, hop constraints, local search heuristics, label correcting algorithms, unmanned vehicles placement
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-110008DOI: 10.3233/978-1-61499-391-9-26ISBN: 978-1-61499-390-2 (tryckt)ISBN: 978-1-61499-391-9 (digital)OAI: oai:DiVA.org:liu-110008DiVA, id: diva2:742139
Konferanse
NATO Advanced Research Workshop (ARW), Examining Robustness and Vulnerability of Critical Infrastructure Networks, Kiev, Ukraine, June 2013
Prosjekter
CADICSELLIITCUASSHERPANFFP6 KISATilgjengelig fra: 2014-08-31 Laget: 2014-08-29 Sist oppdatert: 2018-02-20bibliografisk kontrollert

Open Access i DiVA

Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance(1337 kB)266 nedlastinger
Filinformasjon
Fil FULLTEXT03.pdfFilstørrelse 1337 kBChecksum SHA-512
d95ddfa56f2a5ee49f354579bd6d2d5e3f088282e418d642f2420bea0efdd2fe2a699387d116248461a9967416b70a155d654334dbf38cc88e9360977480730f
Type fulltextMimetype application/pdf

Andre lenker

Forlagets fulltekstFind book in another country/Hitta boken i ett annat land

Personposter BETA

Burdakov, OlegDoherty, PatrickKvarnström, Jonas

Søk i DiVA

Av forfatter/redaktør
Burdakov, OlegDoherty, PatrickKvarnström, Jonas
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 266 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 465 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf