Finding a Noncrossing Steiner Forest in Plane Graphs Under a 2-Face Condition

Yoshiyuki Kusakari (), Daisuke Masubuchi () and Takao Nishizeki ()
Additional contact information
Yoshiyuki Kusakari: Akita Prefectural University
Daisuke Masubuchi: IBM Japan Ltd.
Takao Nishizeki: Tohoku University

Journal of Combinatorial Optimization, 2001, vol. 5, issue 2, No 6, 249-266

Abstract: Abstract Let G = (V,E) be a plane graph with nonnegative edge weights, and let $$\mathcal{N}$$ be a family of k vertex sets $$N_1 ,N_2 ,...,N_k \subseteq V$$ , called nets. Then a noncrossing Steiner forest for $$\mathcal{N}$$ in G is a set $$\mathcal{T}$$ of k trees $$T_1 ,T_2 ,...,T_k$$ in G such that each tree $$T_i \in \mathcal{T}$$ connects all vertices, called terminals, in net N i, any two trees in $$\mathcal{T}$$ do not cross each other, and the sum of edge weights of all trees is minimum. In this paper we give an algorithm to find a noncrossing Steiner forest in a plane graph G for the case where all terminals in nets lie on any two of the face boundaries of G. The algorithm takes time $$O\left( {n\log n} \right)$$ if G has n vertices and each net contains a bounded number of terminals.

Keywords: algorithm; plane graph; noncrossing; Steiner tree (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1011425821069 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:jcomop:v:5:y:2001:i:2:d:10.1023_a:1011425821069

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1011425821069

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

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