Timeline for Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in an undirected graph
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| S Apr 8, 2014 at 11:43 | history | suggested | Saeed | CC BY-SA 3.0 |
Removing unnecessary signs, also changing Hebrew character (which was similar to 'n').
|
| Apr 8, 2014 at 11:37 | review | Suggested edits | |||
| S Apr 8, 2014 at 11:43 | |||||
| Apr 2, 2014 at 7:48 | history | bounty ended | Lior Kogan | ||
| Apr 2, 2014 at 7:48 | vote | accept | Lior Kogan | ||
| Apr 1, 2014 at 14:19 | comment | added | Chandra Chekuri | Try adapting the successive shortest path algorithm (also called Surballe's algorithm for the case of 2 paths which is of interest here). You want to find shortest 2-paths from $y$ (it is better to call it $y$ instead of $y_e$ since it is the same for all edges) to every $x_e$. I think this is doable efficiently by first computing a shortest path tree from $y$ and then implementing the second path computation with some care. | |
| Apr 1, 2014 at 12:36 | history | edited | R B | CC BY-SA 3.0 |
deleted 39 characters in body
|
| Apr 1, 2014 at 11:20 | history | edited | R B | CC BY-SA 3.0 |
added 158 characters in body
|
| Mar 31, 2014 at 11:58 | history | edited | R B | CC BY-SA 3.0 |
added 1 characters in body
|
| Mar 31, 2014 at 9:24 | comment | added | R B | @LiorKogan - if you wish to implement it in practice, try the following trick: Assume that for some $e\in E$ the cost of the flow ( / the length of the shortest s-t path that includes $e$) is $l'\leq l$. 1. All of the edges on the found path are a part of the output graph. 2. Pick a short subpath (of length, say, 1-3), $y$ such that the original path was $P=x\cdot y\cdot z$. Delete $y$ and search for a path/s that connect $x$ with $z$. 3.Repeat for multiple $y$'s. This should create create a "tunnel" of edges around $P$ which need not be examined by themselves. | |
| Mar 31, 2014 at 6:42 | comment | added | Lior Kogan | @RB: Is there some preprocessing that would allow us not to run a full min cost flow algorithm |E| times? | |
| Mar 31, 2014 at 6:34 | comment | added | Lior Kogan | @RB: Thank you. The suggested algorihm may be effective when l is relatively large, but it is probably suboptimal for relatively small values of l. I guess I can trim G first by removing any vertex farther than floor(l/2) from s and ceil(l/2) from t. | |
| Mar 30, 2014 at 6:27 | history | edited | R B | CC BY-SA 3.0 |
added 120 characters in body
|
| Mar 30, 2014 at 2:07 | comment | added | Chandra Chekuri | Sure, I am aware of that solution too - conceptually it is good to understand biconnected components via disjoint paths even though one can find cut-vertices and biconnected components directly via DFS. | |
| Mar 29, 2014 at 22:08 | comment | added | R B | @ChandraChekuri - that is correct, but keep in mind that if the problem doesn't have the length constraint, there's a lot simpler algorithm for deciding it - see here | |
| Mar 29, 2014 at 21:27 | comment | added | Chandra Chekuri | It is easier to understand the argument in the above answer by stripping away the reduction to directed flow. There is a simple path from $s$ to $t$ containing a node $v$ iff there is a path $P$ from $v$ to $s$ and a path $Q$ from $v$ to $t$ such that $P$ and $Q$ are node disjoint except at $v$. This crucially uses the undirectedness. This can be checked via flow and the cost version can also be done via min-cost flow. One can check whether there is a simple path from $s$ to $t$ containing $e$ by introducing a node in the middle of $e$. | |
| Mar 29, 2014 at 15:09 | history | edited | R B | CC BY-SA 3.0 |
deleted 7 characters in body
|
| Mar 29, 2014 at 15:04 | history | answered | R B | CC BY-SA 3.0 |