The algebraic Monge property and path problems

by: Wolfgang Bein, Peter Brucker, Larmore, Park

Discrete Applied Mathematics, Vol. 145, No. 3. (30 January 2005), pp. 455-464.

View FullText article

DOI, ScienceDirect

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

AbnerCYH

Find related articles with these CiteULike tags

algebra, algorithms, graph

Abstract

We give algorithmic results for combinatorial problems with cost arrays possessing certain algebraic Monge properties. We extend Monge-array results for two shortest path problems to a general algebraic setting, with values in an ordered commutative semigroup, if the semigroup operator is strictly compatible with the order relation. We show how our algorithms can be modified to solve bottleneck shortest path problems, even though strict compatibility does not hold in that case. For example, we give a linear time algorithm for the unrestricted shortest path bottleneck problem on n nodes, also O(kn) and O(n3/2 log5/2 n) time algorithms for the k-shortest path bottleneck problem.

@article{citeulike:2581653, abstract = {We give algorithmic results for combinatorial problems with cost arrays possessing certain algebraic Monge properties. We extend Monge-array results for two shortest path problems to a general algebraic setting, with values in an ordered commutative semigroup, if the semigroup operator is strictly compatible with the order relation. We show how our algorithms can be modified to solve bottleneck shortest path problems, even though strict compatibility does not hold in that case. For example, we give a linear time algorithm for the unrestricted shortest path bottleneck problem on n nodes, also O(kn) and O(n3/2 log5/2 n) time algorithms for the k-shortest path bottleneck problem.}, author = {Bein, Wolfgang and Brucker, Peter and Larmore and Park}, citeulike-article-id = {2581653}, doi = {10.1016/j.dam.2004.06.001}, journal = {Discrete Applied Mathematics}, keywords = {algebra, algorithms, graph}, month = {January}, number = {3}, pages = {455--464}, posted-at = {2008-03-24 17:44:05}, priority = {2}, title = {The algebraic Monge property and path problems}, url = {http://dx.doi.org/10.1016/j.dam.2004.06.001}, volume = {145}, year = {2005} }

RIS record

TY - JOUR ID - citeulike:2581653 L3 - citeulike-article-id:2581653 TI - The algebraic Monge property and path problems JF - Discrete Applied Mathematics VL - 145 IS - 3 SP - 455 EP - 464 N2 - We give algorithmic results for combinatorial problems with cost arrays possessing certain algebraic Monge properties. We extend Monge-array results for two shortest path problems to a general algebraic setting, with values in an ordered commutative semigroup, if the semigroup operator is strictly compatible with the order relation. We show how our algorithms can be modified to solve bottleneck shortest path problems, even though strict compatibility does not hold in that case. For example, we give a linear time algorithm for the unrestricted shortest path bottleneck problem on n nodes, also O(kn) and O(n3/2 log5/2 n) time algorithms for the k-shortest path bottleneck problem. KW - algebra KW - algorithms KW - graph AU - Bein, Wolfgang AU - Brucker, Peter AU - Larmore AU - Park PY - 2005/01/30/ UR - http://dx.doi.org/10.1016/j.dam.2004.06.001 ER -

RIS BibTeX