Document Type

Article

Publication Date

Fall 2009

Publication Title

Applied Mathematics and Computation

Volume

215

Issue

1

First Page

353

Last Page

366

Keywords

Edge-weighted-colored multidigraph, Edge-colored paths, Adjacency matrix, Decision making, Status quo analysis, Graph model for conflict resolution

Abstract

An algebraic approach to finding all edge-weighted-colored paths within a weighted colored multidigraph is developed. Generally, the adjacency matrix represents a simple digraph and determines all paths between any two vertices, and is not readily extendable to colored multidigraphs. To bridge the gap, a conversion function is proposed to transform the original problem of searching edge-colored paths in a colored multidigraph to a standard problem of finding paths in a simple digraph. Moreover, edge weights can be used to represent some preference attribute. Its potentially wide realm of applicability is illustrated by a case study: status quo analysis in the graph model for conflict resolution. The explicit matrix function is more convenient than other graphical representations for computer implementation and for adapting to other applications. Additionally, the algebraic approach reveals the relationship between a colored multidigraph and a simple digraph, thereby providing new insights into algebraic graph theory.

Comments

NOTICE: this is the author’s version of a work that was accepted for publication in Applied Mathematics and Computation. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Applied Mathematics and Computation, 215, 1 (2009) http://dx.doi.org/10.1016/j.amc.2009.04.086.

Included in

Business Commons

Share

COinS