All Questions
8 questions
7
votes
7
answers
3k
views
Efficient Hamiltonian cycle algorithms for graph classes
Generally speaking, finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $H$, then we can reduce the problem of finding a Hamiltonian cycle in $G$ to finding an ...
- 6,962
4
votes
1
answer
2k
views
How many edge-disjoint cycles of length 3 are in the complete graph?
A couple of questions related to edge-disjoint cycles.
Let $K_n = (V,E)$ be the complete graph on $|V|=n$ nodes. Two cycles are 'edge disjoint' if they do not share any edges.
What is the size of ...
- 599
3
votes
1
answer
503
views
Compute number vertex disjoint cycles in graph surrounding a face
Hi all,
If anyone has insight into the following variant of the classic problem of packing vertex-disjoint cycle into graphs I would be interested.
Given a finite undirected graph $G$ embedded in $...
- 211
2
votes
3
answers
16k
views
Cycle of length 4 in an undirected graph
Can anyone give me a hint for an algorithm to find a simple cycle of length 4 (4 edges and 4 vertices that is) in an undirected graph, given as an adjacency list? It needs to use $O(v^3)$ operations (...
- 23
2
votes
4
answers
6k
views
Counting simple 4-cycles in an undirected graph [closed]
I'm looking for an algorithm which just counts the number of simple and distinct 4-cycles in an undirected graph labelled with integer keys. I don't need it to be optimal because I only have to use it ...
- 121
2
votes
2
answers
553
views
Need input on a potentially NP-hard maximal edge-weighted multi-cycle graph
I've posted a question on Stack Overflow regarding a seemingly NP-hard problem on maximization of weighted cycles in a graph problem.
One of the respondents cited Professor David Speyer's Math ...
- 21
2
votes
1
answer
82
views
Algorithms for heaviest edge-disjoint cycle collection contained in graph's set of edges
given a biconnected symmetric graph with weighted edges,
what is the algorithmic complexity of determining a set of pairwise edge-disjoint cycles with maximal sum of edge weights if there are no other ...
- 13.2k
2
votes
0
answers
388
views
A fast algorithm for deciding if a given undirected graph contains a C4 subgraph
I'm looking for an algorithm for deciding if a given undirected graph G contains C4 as a sub graph, not necessarily induced. I'm not interested in finding such a cycle, if it exists.
I was told there ...
- 21