patternMinor
Is the optimal order of graph vertices s.t. minimizes edges to later vertices a well-known problem?
Viewed 0 times
problemtheordergraphoptimaledgeslaterwellknownminimizes
Problem
I'm a little unfamiliar with graph theory, and I found an interesting problem in my work that I do not know if its already well-known or can be easily mapped to another one. If I were to express the problem more formally:
Given a directed unweighted graph $\langle V,E \rangle$, find a total order between vertices $v_1
Many thanks in advance :)
Given a directed unweighted graph $\langle V,E \rangle$, find a total order between vertices $v_1
- Can be easily mapped to any other problem?
- If so, there is any good algorithm to solve it?
- Can a good heuristic be computed easily?
Many thanks in advance :)
Solution
Your problem can be mapped to problem of finding minimal set of edges $F$ such that $G\backslash F$ is a DAG (each solution for your problem is a solution for this problem and vice versa). This problem is known as minimum feedback arc set problem and is one of Karp's 21 NP-complete problems
Context
StackExchange Computer Science Q#68894, answer score: 3
Revisions (0)
No revisions yet.