All Questions
Tagged with eulerian-path algorithms
6
questions
-1
votes
1
answer
43
views
What are necessary and sufficient conditions to have a negative cycle in a directed graph with some negative edges? [closed]
Trying to test Johnson’s algorithm with over 100 vertices but it doesn’t work if there is a negative cycle. So I’m trying to write code to construct graphs with some negative weights (about 10% of the ...
- 35
1
vote
1
answer
854
views
Find the shortest route to visit at least once all edges of a undirected weighted non-Eulerian graph
I'm trying to adress the following algorithmic problem using graph theory and Python:
I (personaly) want to find the shortest route I would follow to run through all streets of my district. I don't ...
- 21
3
votes
1
answer
538
views
Algorithm that check if given undirected graph can have Eulerian Cycle by adding edges
Assume that G is a connectable undirected graph, what is the best algorithm in terms of complexity, that check if graph G can have an Eulerian cycle by adding edges?
I thought of their two cases
G ...
- 97
1
vote
1
answer
2k
views
Computational complexity of Eulerian and Hamiltonian paths and cycles in (un)directed graphs
Hey Guys I am aware that we can find if there exists a hamilton path in a directed graph in O(V+E) time using topological sorting.
I was wondering if hamilton cycles, euler paths and euler cycles can ...
- 133
2
votes
0
answers
541
views
Maximal Eulerian subgraph in a given graph
Given a graph like the following:
how do I find the maximal Eulerian subgraph? The answer for this case should be (subgraph with blue edges):
In general, is there an algorithm to derive this ...
- 21
0
votes
0
answers
510
views
Chinese Postman Problem - open walk variation
Consider the following variation of the Chinese postman problem (also known as the route inspection problem). Instead of finding the shortest closed walk which traverses each edge at least once, find ...
- 2,177