Minimal functional routes in directed graphs with dependent edges

Rui Sheng Wang, Zhongyao Sun, Réka Albert

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)391-409
Number of pages19
JournalInternational Transactions in Operational Research
Issue number3
StatePublished - May 2013

All Science Journal Classification (ASJC) codes

  • Business and International Management
  • Computer Science Applications
  • Strategy and Management
  • Management Science and Operations Research
  • Management of Technology and Innovation


Dive into the research topics of 'Minimal functional routes in directed graphs with dependent edges'. Together they form a unique fingerprint.

Cite this