Minimal functional routes in directed graphs with dependent edges

作者：Wang Rui Sheng^*; Sun Zhongyao; Albert Reka

来源：International Transactions in Operational Research, 2013, 20(3): 391-409.

DOI：10.1111/itor.12007

• graph search algorithms
• minimal functional routes
• directed graphs
• dependent edges

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.

• 出版日期2013-5