Minimal functional routes in directed graphs with dependent edges. (8th February 2013)

• Record Type: Journal Article
• Authors: Wang, Rui‐Sheng; Sun, Zhongyao; Albert, Réka
• Is Part Of: International transactions in operational research. Volume 20:Number 3(2013:May)
• Page Start: 391
• Page End: 409
• Publication Date: 2013-02-08
• Subjects: graph search algorithms -- minimal functional routes -- directed graphs -- dependent edges; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12007
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: Graphs are mathematical structures used to model a set of objects and the relations between them. One of the basic concepts of graph theory, the path, has wide real‐world applications. In classic graph models, edges ending at a node are assumed to be independent. However, many real graphs/networks can only be correctly described by considering a dependency among nodes or edges. Paths in such graphs may not be functional if the conditional dependency is ignored. In this study, we investigate the routing problem in directed graphs with dependent edges represented by general graph models as alternatives to hypergraphs. We define a minimal functional route (MFR) as a minimal set of nodes and edges that can independently perform information transfer between two given nodes, and formulate the determination of MFRs as a graph search problem. A depth‐first‐search (DFS) top‐down algorithm, an iterative integer linear programming (ILP) bottom‐up algorithm, and a subgraph‐growing bottom‐up algorithm are devised subsequently to solve this problem. Numerical experiments verify the effectiveness of the algorithms. The defined MFR problem and the proposed algorithms are expected to find many practical applications.