Czech Digital Mathematics Library (Institute of Mathematics CAS) · 2006 · 11 citations · 0 references
Open access
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsDirected Acyclic GraphsGraph AlgorithmsGraph TheoryPartial OrdersShortest Path AlgorithmsShortest Path ProblemsShortest PathsVertex Ordering
To present the decision maker's (DM) preferences in multicriteria decision problems as a partially ordered set is an effective method to catch the DM's purpose and avoid misleading results. Since our paper is focused on minimal path problems, we regard the ordered set of edges (E,): Minimal paths are defined in respect to powerordered sets which provides an essential tool to solve such problems. An algorithm to detect minimal paths on a multicriteria minimal path problem is presented. Keywords minimal paths, bicriterion path problems, multicriteria analysis, power ordered sets, efficient solutions 1 Introduction Weighted graphs play an important role in most combinatorial optimization problems. For a longest path on an acyclic directed graph the weight of an edge may symbolize the duration of time for a step in the schedule of a project. For a shortest path in a network the weights may be distances between locations. In general the weights are values in some scales (km, hours) which m...