Name
Abstract | ||
|---|---|---|
Let G = (V,E) be a plane graph with nonnegative edge weights, and let
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=VW01081001H67X67_html\10878_2004_Article_333492_TeX2GIFIE1.gif" border="0" alt="
$$\mathcal{N}$$
" /> be a family of k vertex sets
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=VW01081001H67X67_html\10878_2004_Article_333492_TeX2GIFIE2.gif" border="0" alt="
$$N_1 ,N_2 ,...,N_k \subseteq V$$
" />, called nets. Then a noncrossing Steiner forest for
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=VW01081001H67X67_html\10878_2004_Article_333492_TeX2GIFIE3.gif" border="0" alt="
$$\mathcal{N}$$
" /> in G is a set
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=VW01081001H67X67_html\10878_2004_Article_333492_TeX2GIFIE4.gif" border="0" alt="
$$\mathcal{T}$$
" /> of k trees
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=VW01081001H67X67_html\10878_2004_Article_333492_TeX2GIFIE5.gif" border="0" alt="
$$T_1 ,T_2 ,...,T_k$$
" /> in G such that each tree
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=VW01081001H67X67_html\10878_2004_Article_333492_TeX2GIFIE6.gif" border="0" alt="
$$T_i \in \mathcal{T}$$
" /> connects all vertices, called terminals, in net Ni, any two trees in
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=VW01081001H67X67_html\10878_2004_Article_333492_TeX2GIFIE7.gif" border="0" alt="
$$\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
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=VW01081001H67X67_html\10878_2004_Article_333492_TeX2GIFIE8.gif" border="0" alt="
$$O\left( {n\log n} \right)$$
" /> if G has n vertices and each net contains a bounded number of terminals. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1023/A:1011425821069 | J. Comb. Optim. |
Keywords | Field | DocType |
algorithm,plane graph,noncrossing,Steiner tree | Binary logarithm,Discrete mathematics,Graph,Combinatorics,Tree (graph theory),Vertex (geometry),Steiner tree problem,Planar graph,Mathematics,Steiner forest,Bounded function | Journal |
Volume | Issue | ISSN |
5 | 2 | 1573-2886 |
Citations | PageRank | References |
1 | 0.36 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yoshiyuki Kusakari | 1 | 10 | 3.34 |
| Daisuke Masubuchi | 2 | 2 | 0.74 |
| Takao Nishizeki | 3 | 1771 | 267.08 |