A matrix-based approach to searching colored paths in a weighted colored multidigraph

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 g...

Full description

Saved in:
Bibliographic Details
Published in:Applied mathematics and computation 2009-09, Vol.215 (1), p.353-366
Main Authors: Xu, Haiyan, Li, Kevin W., Marc Kilgour, D., Hipel, Keith W.
Format: Article
Language:English
Subjects:
Adjacency matrix
Algebra
Combinatorics
Combinatorics. Ordered structures
Decision making
Edge-colored paths
Edge-weighted-colored multidigraph
Exact sciences and technology
Graph theory
Linear and multilinear algebra, matrix theory
Mathematical analysis
Mathematics
Numerical analysis
Numerical analysis. Scientific computation
Sciences and techniques of general use
Status quo analysis, Graph model for conflict resolution
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0096-3003
1873-5649
DOI:10.1016/j.amc.2009.04.086