Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.ORCID iD: 0000-0003-1836-4200
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, The Institute of Technology.ORCID iD: 0000-0002-5500-8494
2014 (English)In: Examining Robustness and Vulnerability of Networked Systems / [ed] Butenko, S., Pasiliao, E.L., Shylo, V., IOS Press, 2014, 26-50 p.Conference paper, Published paper (Refereed)
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.

Place, publisher, year, edition, pages
IOS Press, 2014. 26-50 p.
Series
NATO Science for Peace and Security Series - D: Information and Communication Security, ISSN 1874-6268 (print), 1879-8292 (online) ; 37
Keyword [en]
Steiner trees, hop constraints, local search heuristics, label correcting algorithms, unmanned vehicles placement
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-110008DOI: 10.3233/978-1-61499-391-9-26ISBN: 978-1-61499-390-2 (print)ISBN: 978-1-61499-391-9 (electronic)OAI: oai:DiVA.org:liu-110008DiVA: diva2:742139
Conference
NATO Advanced Research Workshop (ARW), Examining Robustness and Vulnerability of Critical Infrastructure Networks, Kiev, Ukraine, June 2013
Projects
CADICSELLIITCUASSHERPANFFP6 KISA
Available from: 2014-08-31 Created: 2014-08-29 Last updated: 2017-02-10Bibliographically approved

Open Access in DiVA

Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance(1337 kB)213 downloads
File information
File name FULLTEXT03.pdfFile size 1337 kBChecksum SHA-512
d95ddfa56f2a5ee49f354579bd6d2d5e3f088282e418d642f2420bea0efdd2fe2a699387d116248461a9967416b70a155d654334dbf38cc88e9360977480730f
Type fulltextMimetype application/pdf

Other links

Publisher's full textFind book in another country/Hitta boken i ett annat land

Search in DiVA

By author/editor
Burdakov, OlegDoherty, PatrickKvarnström, Jonas
By organisation
Optimization The Institute of TechnologyArtificial Intelligence and Integrated Computer Systems
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 213 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 191 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf