Estimating All Pairs Shortest Paths in Restricted Graph Families: A Unified Approach Export

@incollection{citeulike:2919306, 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.}, author = {Dragan, Feodor}, citeulike-article-id = {2919306}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/3-540-45477-2_11}, doi = {10.1007/3-540-45477-2_11}, journal = {Graph-Theoretic Concepts in Computer Science}, keywords = {algorihms, all-pairs-shortest-paths, yrbcn}, pages = {103--116}, posted-at = {2008-06-23 17:55:24}, priority = {2}, title = {Estimating All Pairs Shortest Paths in Restricted Graph Families: A Unified Approach}, url = {http://dx.doi.org/10.1007/3-540-45477-2_11}, year = {2001} }

TY - CHAP ID - citeulike:2919306 L3 - citeulike-article-id:2919306 N2 - 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. JF - Graph-Theoretic Concepts in Computer Science EP - 116 TI - Estimating All Pairs Shortest Paths in Restricted Graph Families: A Unified Approach SP - 103 KW - algorihms KW - all-pairs-shortest-paths KW - yrbcn AU - Dragan, Feodor PY - 2001/// UR - http://dx.doi.org/10.1007/3-540-45477-2_11 ER -