The 1-Center Problem: Exploiting Block Structure

M.-L. Chen, R. L. Francis and T. J. Lowe
Additional contact information
M.-L. Chen: Northeastern Illinois University, Chicago, Illinois 60625
R. L. Francis: The University of Florida, Gainesville, Florida 32601
T. J. Lowe: Purdue University, West Lafayette, Indiana 47907

Transportation Science, 1988, vol. 22, issue 4, 259-269

Abstract: A block of a graph is a maximal nonseparable subgraph. We show how the knowledge of block structure can be used to help solve the nonlinear 1-center problem on graphs which are more general than trees. We give an efficient algorithm which either finds a unique 1-center at some vertex, or else localizes the search for all 1-centers to a single block. The algorithm makes use of an associated graph, called a blocking graph, which is a tree, and iteratively orients arcs in the blocking graph to “point the way” to a block which contains all 1-centers.

Date: 1988
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.22.4.259 (application/pdf)

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:inm:ortrsc:v:22:y:1988:i:4:p:259-269

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().