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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bullitt, E., Aylward, S., Liu, A., Stone, J., Mukherji, S., Coffey, C., Gerig, G., Pizer, S.: 3D graph description of the intracerebral vasculature from segmented MRA and tests of accuracy by comparison with X-ray angiograms. In: Kuba, A., Sámal, M., Todd-Pokropek, A. (eds.) Proceedings of IPMI. LNCS, vol. 1613, pp. 308–321. Springer, Berlin (1999)
Jiang, Y., Zhuang, Z., Sinusas, A., Staib, L., Papademetris, X.: Vessel connectivity using Murray’s hypothesis. In: Fichtinger, G., Martel, A., Peters, T. (eds.) Proceedings of MICCAI 2011. LNCS, vol. 6893, pp. 528–536. Springer, Berlin (2011)
Jomier, J., Ledigarcher, V., Aylward, S.: Automatic vascular tree formation using the Mahalanobis distance. In: Duncan, J., Gerig, G. (eds.) Proceedings of MICCAI 2005. LNCS, vol. 3750, pp. 806–812. Springer, Berlin (2005)
Murray, C.: The physiological principle of minimum work, I. the vascular system and the cost of blood volume. Proc. Natl. Acad. Sci. 12(3), 207–214 (1926)
Szymczak, A., Stillman, A., Tannenbaum, A., Mischaikow, K.: Coronary vessel trees from 3D imagery: a topological approach. Med. Image Anal. 10(4), 548–559 (2006)
Vasko, F., Barbieri, R., Rieksts, B., Reitmeyer, K., Stott, K.: The cable trench problem: combining the shortest path and minimum spanning tree problems. Comput. Oper. Res. 29(5), 441–458 (2002)
Vasko, F., Landquist, E., Kresge, G., Tal, A., Jiang, Y., Papademetris, X.: A simple and efficient strategy for solving very large-scale generalized cable-trench problems. Netw. Int. J. 67(3), 199–208 (2016)
Zagorchev, L., Oses, P., Zhuang, Z., Moodie, K., Mulligan-Kehoe, M., Simons, M., Couffinhalt, T.: Micro computed tomography for vascular exploration. J. Angiogenesis Res. 2(1), 7 (2010)
Acknowledgements
The authors thank Dr. Albert Sinusas and Zhenwu Zhuang, Yale University School of Medicine, for providing microCT scan image data of a mouse leg for our experiments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Landquist, E., Vasko, F.J., Kresge, G., Tal, A., Jiang, Y., Papademetris, X. (2018). The Generalized Steiner Cable-Trench Problem with Application to Error Correction in Vascular Image Analysis. In: Fink, A., Fügenschuh, A., Geiger, M. (eds) Operations Research Proceedings 2016. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-319-55702-1_52
Download citation
DOI: https://doi.org/10.1007/978-3-319-55702-1_52
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-55701-4
Online ISBN: 978-3-319-55702-1
eBook Packages: Business and ManagementBusiness and Management (R0)