Complexity and Algorithms in Graphs

Reachability-Preserving Minimum Edge Cut Problem and Applications in Biology

The paper introduces the Reachability Preserving Minimum Edge Cut problem to model biological pathway interventions, showing when fast algorithms work and when exact methods are needed.

Accurate Flow Decomposition via Robust Integer Linear Programming

This paper introduces an Integer Linear Programming formulation for accurate flow decomposition in the presence of errors, showing improved accuracy over previous methods.

Directed Shortest Walk on Temporal Graphs

The paper defines and solves the Time Conditioned Shortest Walk problem on temporal graphs, showing it is NP-Hard and introducing an integer linear program to address it.

Connectivity Problems on Heterogeneous Graphs

The paper introduces the condition Steiner network problem to address dynamic biological networks across multiple conditions and develops an integer linear programming solver for it.

Efficient Heuristic for Decomposing a Flow with Minimum Number of Paths

The paper introduces an efficient heuristic for decomposing a flow into the minimum number of paths, showing significant improvement over previous methods in both simulated and transcript assembly scenarios.