All Questions
Tagged with enumeration optimization
7 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 ...
1
vote
0
answers
44
views
What do you call a greedy algorithm that solves a combinatorial problem by optimizing the best k>1 choices altogether?
Suppose you have a problem which goal is to find the permutation of some set $S$ given in input that minimizes an objective function $f$ (for example the Traveling Salesman problem).
A trivial ...
- 623
2
votes
0
answers
305
views
Greedy Algorithm to return multiple optimal solutions
How would one go about enumerating all the optimal answers for interval scheduling?
Not sure what to begin with, my guess is to use the other approaches i.e. earliest start time, shortest interval ...
- 21
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
1
vote
0
answers
86
views
Can smart recursive search find all optimal solutions for Closest String?
Consider the Closest String problem:
Input: Strings $s_1, \dots, s_m \in \Sigma^n$ and $k \in \mathbb{N}$.
Question: Is there $s \in \Sigma^n$ for which $d_H(s, s_i) \leq k$
for all $i \in ...
- 72.9k