Add to ORKGKarger, Motwani and Ramkumar have shown that there is no constant approximation algorithm to find a longest cycle in a Hamiltonian graph, and they conjectured this is the case even for graphs with bounded degree. On the other hand, Feder, Motwani and Subi have shown that there is a polynomial time algorithm for finding a cycle of length n log 3 2 in a 3-connected cubic n-vertex graph. In this paper, we show that if G is a 3-connected n-vertex graph with maximum degree at most d, then one can find, in O(n³) time, a cycle in G of length at least Ω(n log b²), where b = 2(d − 1)² + 1
Abstract: Let G be a graph of order n satisfying d(u) + d(v) n for every edge uv of G. We show tha...
Let G be a graph of order n satisfying d(u) + d(v) n for every edge uv of G. We show that the circum...
The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle pas...
Karger, Motwani, and Ramkumar [Algorithmica, 18 (1997), pp. 82–98] have shown that there is no const...
In 1993, Jackson and Wormald conjectured that if G is a 3-connected n-vertex graph with maximum degr...
We show how to find in Hamiltonian graphs a cycle of length nΩ(1 / log logn). This is a consequence ...
AbstractWe show how to find in Hamiltonian graphs a cycle of length nΩ(1/loglogn)=exp(Ω(logn/loglogn...
AbstractWe show how to find in Hamiltonian graphs a cycle of length nΩ(1/loglogn)=exp(Ω(logn/loglogn...
AbstractN. Alon [J. Graph Theory 10 (1986), 123–127] proved that if the minimum degree of a graph G ...
AbstractThe length of a longest cycle in a graph G is called the circumference of G and is denoted b...
AbstractIn this paper, we consider the length of the longest cycle through specified vertices. We sh...
We investigate the computational hardness of approximating the longest path and the longest cycle in...
In 1999, Jacobson and Lehel conjectured that, for k >= 3, every k-regular Hamiltonian graph has cycl...
In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a ...
AbstractThe length of a longest cycle in a graph G is called the circumference of G and is denoted b...
Abstract: Let G be a graph of order n satisfying d(u) + d(v) n for every edge uv of G. We show tha...
Let G be a graph of order n satisfying d(u) + d(v) n for every edge uv of G. We show that the circum...
The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle pas...
Karger, Motwani, and Ramkumar [Algorithmica, 18 (1997), pp. 82–98] have shown that there is no const...
In 1993, Jackson and Wormald conjectured that if G is a 3-connected n-vertex graph with maximum degr...
We show how to find in Hamiltonian graphs a cycle of length nΩ(1 / log logn). This is a consequence ...
AbstractWe show how to find in Hamiltonian graphs a cycle of length nΩ(1/loglogn)=exp(Ω(logn/loglogn...
AbstractWe show how to find in Hamiltonian graphs a cycle of length nΩ(1/loglogn)=exp(Ω(logn/loglogn...
AbstractN. Alon [J. Graph Theory 10 (1986), 123–127] proved that if the minimum degree of a graph G ...
AbstractThe length of a longest cycle in a graph G is called the circumference of G and is denoted b...
AbstractIn this paper, we consider the length of the longest cycle through specified vertices. We sh...
We investigate the computational hardness of approximating the longest path and the longest cycle in...
In 1999, Jacobson and Lehel conjectured that, for k >= 3, every k-regular Hamiltonian graph has cycl...
In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a ...
AbstractThe length of a longest cycle in a graph G is called the circumference of G and is denoted b...
Abstract: Let G be a graph of order n satisfying d(u) + d(v) n for every edge uv of G. We show tha...
Let G be a graph of order n satisfying d(u) + d(v) n for every edge uv of G. We show that the circum...
The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle pas...