Structural Properties of Minimum Multi-source Multi-Sink Steiner Networks in the Euclidean Plane

Alexander Westcott, Marcus Brazil and Charl Ras ()
Additional contact information
Alexander Westcott: University of Melbourne
Marcus Brazil: University of Melbourne
Charl Ras: University of Melbourne

Journal of Optimization Theory and Applications, 2023, vol. 197, issue 3, No 10, 1104-1139

Abstract: Abstract Given two finite sets A and B of points in the Euclidean plane, a minimum multi-source multi-sink Steiner network in the plane, or a minimum (A, B)-network, is a directed graph embedded in the plane with a dipath from every node in A to every node in B such that the total length of all arcs in the network is minimised. Such a network may contain Steiner points—nodes appearing in the solution that are neither in A nor B. We show that for any finite point sets A, B in the plane, there exists a minimum (A, B)-network that is constructible by straightedge and compass (this was claimed in a paper by Maxwell and Swanepoel, but their argument is incorrect). We use this property to formulate an algorithmic framework for exactly finding minimum (A, B)-networks in the Euclidean plane. We also present several new structural and geometric properties of minimum (A, B)-networks. In particular, we resolve a conjecture of Alfaro by proving that, for any terminal set A, adding an appropriate orientation to the edges of a minimum 2-edge-connected Steiner network on A yields a minimum (A, A)-network.

Keywords: Directed Steiner networks; Steiner trees; Exact algorithm; Alfaro’s conjecture; Geometric networks (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-023-02203-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:joptap:v:197:y:2023:i:3:d:10.1007_s10957-023-02203-6

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-023-02203-6

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().