Skip to content
master
Switch branches/tags
Go to file
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
 
 
 
 

README.md

O(n) algorithm for computing longest paths in 2-trees

Clojars Project

cljdoc badge

Overview

In 2013 Markov, Vassilev and Manev published a novel linear time algorithm for computing longest paths in 2-trees.

This repository contains 3 implementations of said algorithm in Clojure:

The first one is a direct implementation of the mathematical operations described in the paper. Due to the need to construct subgraphs to implement splitting, the time complexity is O(n√n).

The second one was suggested by Minko Markov and preprocesses the 2-tree, thus avoiding the need to construct subgraphs. The time complexity is O(n). Due to its recursive nature, this implementation will fail with a Stack Overflow Error if used on deep 2-trees with millions of vertices.

The third implementation is an iterative one. It uses the EdgeLabels map as a sort of explicit call stack. The time complexity is O(n).

Only the third one should be used for any practical purposes.

Data representation

The vertices of the graph are represented as positive integers.

On an abstract lever, the graph is represented as an adjacency list.

On a concrete level, it's a int-map in which a vertex acts as key and the corresponding values is an int-set of the its neighbours.