Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [eulerian-paths]

Questions related to Eulerian paths on graphs. A path is Eulerian if it visits each edge exactly once.

0
votes
0answers
32 views

Hamilton path and Euler circuits in Cycle graph

Can $C_n$ has $2*n$ Euler circuits and $3*n$ Hamilton paths in the Cyclic graphs?
0
votes
2answers
205 views

Time Complexity and graphs

I'm learning graphs these days and need to clear few doubts- Can I determine weather 5 points in two dimensions whose X and Y coordinates are given lie on the same straight line in O(1). What is the ...
0
votes
1answer
13 views

Distribute to pairs with efficient algorithms

The task is to find a efficient algorithm to the following problem. There are n boys and n girls who need to be divided to pairs. You get a list with all possible pairs that could be made. It means ...
4
votes
1answer
59 views

Longest path with limited edge traversals

Given a graph where each edge has a capacity, is there an efficient algorithm to find the longest path in the graph which does not pass through an edge more times than its capacity? The exact problem ...
0
votes
1answer
180 views

Optimizing Fleury's algorithm to work in O(|V|+|E|)

The time complexity of Fleury's algorithm is $O(|E|^2)$ because for each edge I have to check whether it is a bridge or not and that takes $O(|V|+|E|)$ time. But, instead of that if I store my bridges ...
4
votes
2answers
96 views

Algorithm for determining if there is exactly one Eulerian path

Given a directed graph such that at least an Eulerian path exists, how to determine efficiently if there is exactly one Eulerian path? Of course if there is an Eulerian circuit then there is more ...
0
votes
0answers
82 views

Enumerating path variations

I have a graph and I'm trying to enumerate all paths that start at node $S$, end at node $E$, uses each edge, and minimizes the number of edges used (i.e. it can only re-use an edge if strictly ...
1
vote
0answers
318 views

Euler circuit for undirected graph versus directed graph

I'm working on finding an Euler circuit for an indoor geographical 2D grid. when abstracting the grid as a an undirected graph, all nodes in the graph are connected (i.e, there is a path between every ...
1
vote
1answer
47 views

Is it possible to turn an eulerian NFA into a linear size DFA?

In general, there exists NFAs of size n whose smallest equivalent DFA requires 2^n states. But if we restrict ourselves to NFAs whose graph is eulerian, is it possible to turn any such NFA of size n ...
1
vote
0answers
45 views

Euler Circuit with least deviation from input

So given an undirected graph stored in form adjacency list using vector<int> adj[], I have to print the Euler Cicuit. Every edge is given as follows ...
1
vote
1answer
2k views

what is edge-disjoint cycles in graph?

I was reading something about Eulerian Tour and there is one property claiming that: An undirected graph can be decomposed into edge-disjoint cycles if and only if all of its vertices have even ...
0
votes
0answers
182 views

Reducibility of finding Eulerian Path to Linear Programming

Consider any arbitrary directed, acyclic graph; how can we formulate the problem of finding a particular Eulerian path as a linear programming problem? It seems like there should be a relatively ...
2
votes
1answer
574 views

Count the number of Euler PATHs in directed graph?

I would like to find all Euler PATHs in a directed graph. Counting (instead of finding) all the Euler PATHs is sufficient. Circuits are not good for me, only Paths. I am doing a problem, that I have ...
2
votes
0answers
293 views

Sampling random graphs with Eulerian paths

How to generate random graphs with eulerian Paths? Its well known that there is a eulerian path if the number of nodes with odd degree is exactly 2 or zero. I'm interested in an algorithm to make ...
1
vote
0answers
160 views

Understanding the correctness of the Euler Tour Technique

I can't prove the correctness of the following algorithm by R. E. Tarjan amd U. Vishkin, as described on wikipedia: Given an undirected tree presented as a set of edges, the Euler tour ...
2
votes
2answers
278 views

Finding valid permutation using a graph

Let $A$ be a set of integers: $A=\left \{ x_1, x_2...x_n \mid 10<x_i<100\right \}$ A valid permutation $x_{i_1}x_{i_2}...x_{i_n}$ is a permutation that holds the following property: For every ...
0
votes
1answer
180 views

Find a continuous path filling whole 3xN grid going through certain points in given order

I've got a grid consisting of squares that is 3 squares high and N squares long. Some of the squares are filled with numbers that are not greater than 3*N. You can move only to squares that are below,...
1
vote
1answer
682 views

Improve worst case time of depth first search on Euler graphs

How to improve the worst case scenario for a depth first search on an Euler graph, starting at some point and ending at that same point? I need to do the whole search but it is not fast enough for ...
9
votes
1answer
298 views

Euler cycles in biconnected components

If a graph has a Euler cycle, do the biconnected components have Euler cycles as well?