Loading...
The P-Center And The P-Median Problems In Graphs With Small Number ' Of Spanning Trees
Citations
Altmetric:
Video URL
Date
1996
Author
Files
Abstract
In this paper, we will describe some algorithms and give their complexity as following:
(1) The algorithm for finding a dominating set of radius r in a vertex-weighted graph with small number of spanning tress.
The complexity of this algorithm for the unicyclic graph is O(m.n).
(2) The algorithm for finding an absolute and vertex p-center of a vertex-weighted graph with small number of spanning
trees. The complexity of determining the p-center is O(m.n2 Ign) for absolute (resp., O(n2 Ign) for vertex) p-center in
unicyclic graphs.
(3) The algorithm for finding a p-median in a vertex-weighted graph with mall number of spanning tress. The complexity of
this algorithm for the class of unicyclic graphs is O(m.n2.p2)