Find Subtrees of Specified Weight and Cycles of Specified Length in Linear Time

02/18/2019
by   On-Hei Solomon Lo, et al.
0

We introduce a variant of DFS which finds subtrees of specified weight in linear time, by which, as observed by Mohr, cycles of specified length in planar hamiltonian graphs can be found. We show, for example, that every planar hamiltonian graph G with minimum degree δ≥ 4 has a cycle of length k for every k ∈{|V(G)|/2, ..., |V(G)|/2 + 3} with 3 ≤ k ≤ |V(G)|, that every planar hamiltonian graph G with δ≥ 5 has a cycle of length k for every k ∈{1/4|V(G)|, ..., 3/4|V(G)| + 3} with 3 ≤ k ≤ |V(G)|, and that if |V(G)| ≥ 8 is even, every 3-connected planar hamiltonian graph G with δ≥ 4 has a cycle of length |V(G)|/2 - 1 or |V(G)|/2 - 2. Each of these cycles can be found in linear time if a Hamilton cycle of the graph is given. Another interesting consequence follows from our tool is that, given an instance of the number partitioning problem, i.e. a multiset of positive integers {a_1, ..., a_N}, if ∑_i = 1^N a_i ≤ 2N - 2, then a partition always exists and can be found in linear time.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset