# Questions tagged [eulerian-paths]

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

19 questions
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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,...
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 ...
1answer
298 views

### Euler cycles in biconnected components

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