The Generalized Steiner Cable-Trench Problem with Application to Error Correction in Vascular Image Analysis

Eric Landquist (), Francis J. Vasko (), Gregory Kresge (), Adam Tal (), Yifeng Jiang () and Xenophon Papademetris ()
Additional contact information
Eric Landquist: Kutztown University
Francis J. Vasko: Kutztown University
Gregory Kresge: Kutztown University
Adam Tal: Kutztown University
Yifeng Jiang: Yale University
Xenophon Papademetris: Yale University

A chapter in Operations Research Proceedings 2016, 2018, pp 391-397 from Springer

Abstract: Abstract The Cable-Trench Problem (CTP) is the problem of minimizing the cost to connect buildings on a campus to a central server so that each building is connected directly to the server via a dedicated underground cable. The CTP is modeled by a weighted graph in which the vertices represent buildings and the edges represent the possible routes for digging trenches and laying cables between two buildings. In this paper, we define the Generalized Steiner CTP (GSCTP), which considers the situation in which a subset of the buildings is connected to the server and also the possibility that trench costs vary because of vegetation or physical obstacles, for example. The GSCTP has several natural applications, but we will focus on its nontrivial and novel application to the problem of digitally connecting microCT scan data of a vascular network with fully automated error correction. The CTP and its variants are NP-hard. However, we show that modifications to Prim’s algorithm find nearly optimal solutions to the GSCTP efficiently.

Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-55702-1_52

Ordering information: This item can be ordered from
http://www.springer.com/9783319557021

DOI: 10.1007/978-3-319-55702-1_52

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().