Name
Abstract | ||
|---|---|---|
<P>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.</P> |
Year | DOI | Venue |
|---|---|---|
1988 | 10.1287/trsc.22.4.259 | Transportation Science |
Keywords | Field | DocType |
algorithms,location | Block graph,Combinatorics,Mathematical optimization,Line graph,Forbidden graph characterization,Graph factorization,Distance-hereditary graph,Null graph,Butterfly graph,Windmill graph,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 4 | 0041-1655 |
Citations | PageRank | References |
4 | 0.44 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| M.-L. Chen | 1 | 4 | 0.78 |
| R. L. Francis | 2 | 251 | 43.33 |
| T. J. Lowe | 3 | 104 | 19.78 |