GitHub - zayd/mlst: Maximum Leaf Spanning Tree Algorithm

Branches Tags

Name		Name	Last commit message	Last commit date
Latest commit History 133 Commits
class-scripts		class-scripts
handler-scripts		handler-scripts
instances		instances
notes		notes
Mlst.py		Mlst.py
Mlst.pyc		Mlst.pyc
README		README
team.txt		team.txt

Repository files navigation

Maximum Leaf Spanning Tree

Implementation of Lu & Ravi approximation algorithm for a maximum leaf spanning tree using NetworkX. Original problem is NP-Complete, algorithm approximates correct solution to within a constant factor of optimal solution.