All Questions
4 questions
4
votes
0
answers
56
views
Using graph symmetries to speed up subgraph enumeration
I have an undirected graph $G$. It has some symmetries in the sense that I know it's automorphism group $\text{Aut}(G)$. I am searching for a specific subgraph defined by some constraints $\phi$ and ...
2
votes
1
answer
331
views
Linear time algorithm for finding $k$ shortest paths in unweighted graphs
Definition. Given an unweighted graph $G=(V,E)$ and two vertices $s$ and $t$,
the $k$-shortest-paths problem is finding the $k$ shortest simple paths
between $s$ and $t$ in $G$.
Note that the ...
- 1,944
8
votes
1
answer
1k
views
Linear time algorithm for finding $k$ shortest paths from $s$ to $t$
Definition. Given a graph $G=(V,E)$ and two vertices $s$ and $t$,
the $k$-shortest-paths problem is finding the $k$ shortest simple paths
between $s$ and $t$ in $G$.
Note that the length of ...
- 1,944
3
votes
0
answers
65
views
Enumerate all minimum feedback arc sets
I am looking for (practically) efficient algorithms to enumerate all minimum feedback arc sets of a directed graph. What algorithms should I look at, with practical implementations in mind?
...
- 128