Journal article
1-center problem: Exploiting block structure
Transportation science, Vol.22(4), pp.259-269
11/01/1988
DOI: 10.1287/trsc.22.4.259
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.
Details
- Title: Subtitle
- 1-center problem: Exploiting block structure
- Creators
- M. L. Chen - Northeastern Illinois UniversityR. L. Francis - University of FloridaT. J. Lowe - Purdue University West Lafayette
- Resource Type
- Journal article
- Publication Details
- Transportation science, Vol.22(4), pp.259-269
- DOI
- 10.1287/trsc.22.4.259
- ISSN
- 0041-1655
- eISSN
- 1526-5447
- Number of pages
- 11
- Language
- English
- Date published
- 11/01/1988
- Academic Unit
- Business Analytics
- Record Identifier
- 9984963103902771
Metrics
1 Record Views