Computer Science – Discrete Mathematics
Scientific paper
2008-01-11
Computer Science
Discrete Mathematics
16 pages, 3 figures
Scientific paper
Network flow interdiction analysis studies by how much the value of a maximum flow in a network can be diminished by removing components of the network constrained to some budget. Although this problem is strongly NP-complete on general networks, pseudo-polynomial algorithms were found for planar networks with a single source and a single sink and without the possibility to remove vertices. In this work we introduce pseudo-polynomial algorithms which overcome some of the restrictions of previous methods. We propose a planarity-preserving transformation that allows to incorporate vertex removals and vertex capacities in pseudo-polynomial interdiction algorithms for planar graphs. Additionally, a pseudo-polynomial algorithm is introduced for the problem of determining the minimal interdiction budget which is at least needed to make it impossible to satisfy the demand of all sink nodes, on planar networks with multiple sources and sinks satisfying that the sum of the supplies at the source nodes equals the sum of the demands at the sink nodes. Furthermore we show that the k-densest subgraph problem on planar graphs can be reduced to a network flow interdiction problem on a planar graph with multiple sources and sinks and polynomially bounded input numbers. However it is still not known if either of these problems can be solved in polynomial time.
No associations
LandOfFree
Extensions to Network Flow Interdiction on Planar Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Extensions to Network Flow Interdiction on Planar Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extensions to Network Flow Interdiction on Planar Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-547667