×

zbMATH — the first resource for mathematics

A note on locating a central vertex of a 3-cactus graph. (English) Zbl 0699.90030
This paper examines two location problems on vertex-weighted networks (graphs with edge-lengths, on which distance is calculated as shortest path distance). The minimum weighted vertex variance problem asks for the vertex at which the variance of the weighted distances to all vertices is minimized, while the vertex restricted stochastic queue median problem is to determine the vertex minimizing the mean service time from there to customer calls at each vertex, which occur independently as Poisson processes and are served as a queue.
Known algorithms solving these problems in time linear in the number of vertices for tree networks are extended here to linear time algorithms on 3-cactus networks, i.e. networks in which the biconnected components consist of at most three vertices. This is achieved by a linear time transformation of the 3-cactus network to a tree on which shortest path- lengths are preserved.
Reviewer: F.Plastria

MSC:
90B05 Inventory, storage, reservoirs
90C35 Programming involving graphs or networks
05C05 Trees
90B22 Queues and service in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Koontz, W.L.G., Economie evaluation of loop feeder relief alternatives, Bell syst. techn. J., 59, 277-281, (1980)
[2] O. Maimon and R. K. Kincaid, Material handling system design for flexible manufacturing systems: a network approach. Working paper, Department of Mathematics, College of William and Mary, Williamsburg, VA 23185.
[3] R. K. Kincaid and T. J. Lowe, The absolute center problem on treelike graphs: a transformation approach. Eur. J. Opl Res. In press.
[4] R. K. Kincaid, Finding two centers of graphs that are almost trees. Submitted for publication.
[5] Gurevich, Y.; Stockmeyer, L.; Vishkin, U., Solving NP-hard problems on graphs that are almost trees and an application to facility location, J. ass. comput. machinery, 31, 459-473, (1984) · Zbl 0629.68042
[6] Chen, M.-L.; Francis, R.L.; Lawrence, J.F.; Lowe, T.J.; Tufekci, S., Block-vertex duality and the one-Median problem, Networks, 15, 395-412, (1986) · Zbl 0647.90031
[7] Halpern, J.; Maimon, O., Accord and conflict among several objectives in locational decisions on tree networks, ()
[8] Maimon, O., The variance equity measures in locational decisions on trees, Ann. opns res., 6, 147-160, (1986)
[9] Herman, O.; Larson, R.C.; Chiu, S.S., Optimal server location on a network operating as an M/G/1 queue, Opns res., 33, 746-771, (1985) · Zbl 0576.90031
[10] R. Batta, The stochastic queue median over a finite discrete set. Opns Res. In press. · Zbl 0675.90027
[11] Chiu, S.S.; Berman, O.; Larson, R.C., Locating a mobile server queueing network facility on a tree network, Mgmt sci., 31, 764-772, (1985) · Zbl 0609.90036
[12] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[13] Handler, G.Y.; Mirchandani, P.B., Location on networks: theory and algorithms, (1979), MIT Press Cambridge, MA · Zbl 0533.90026
[14] Tarjan, R., Depth first search and linear graph algorithms, SIAM J. comput, 1, 146-160, (1972) · Zbl 0251.05107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.