Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10332228 | Journal of Algorithms | 2005 | 21 Pages |
Abstract
In this paper we show that a very simple and efficient approach can be used to solve the all pairs almost shortest path problem on the class of weakly chordal graphs and its different subclasses. Moreover, this approach works well also on graphs with small size of largest induced cycle and gives a unified way to solve the all pairs almost shortest path and all pairs shortest path problems on different graph classes including chordal, strongly chordal, chordal bipartite, and distance-hereditary graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Feodor F. Dragan,