|
|
An efficient algorithm to compute a Steiner set and Steiner tree on trapezoid graphs.(Report)
- Article from:
-
Tamsui Oxford Journal of Mathematical Sciences
- Article date:
-
May 1, 2008
- Author:
-
;
|
Copyright informationCOPYRIGHT 2008 Aletheia University. This material is published under license from the publisher through the Gale Group, Farmington Hills, Michigan. All inquiries regarding rights should be directed to the Gale Group. (Hide copyright information)
|
This paper presents an efficient algorithm to compute a minimum cardinality Steiner set and Steiner tree on trapezoid graphs. The algorithm takes O(m + n[square root of (log C)]) time for a trapezoid graph with n vertices and m edges, where cost of each arc is a non-negative integer number bounded by C.
Keywords and Phrases: Design and analysis of algorithms, Spanning tree, Steiner set, Steiner tree, Trapezoid graph.
1. Introduction
A trapezoid [T.sub.i] is defined by fore corner points [[a.sub.i], [b.sub.i], [c.sub.i], [d.sub.i]], where [a.sub.i]
[FIGURE 1 OMITTED]
graphs and the interval graphs (9). The permutation graphs are obtained in the case where [a.sub.i] = ...