How Tree-like are Road Networks?
Project 2024-25
Project Title: How Tree-like are Road Networks?
Lab/Research Group: Theory Group
The theory group consists of eight faculty members (plus four adjuncts) who use mathematical techniques to study problems throughout computer science. We work on network algorithms, coding theory, combinatorial optimization, computational geometry, data streams, dynamic algorithms and complexity, model checking and static analysis, database theory, descriptive complexity, parallel algorithms and architectures, and computational complexity theory. Members of the theory group wear other hats as well and collaborate throughout the department and the world beyond. For more details of the myriad work going on, please visit our web-pages.
You can find more about the group and the weekly seminars at https://groups.cs.umass.edu/theory/
Project Description:
Trees are very simple graphs: they are connected and have no cycles. However, most practical networks are not trees. But they could be tree-like. A tree treewidth is a graph parameter that measures how similar a graph is to a tree. Graphs that have a smaller treewidth are more similar to trees. Being close to a tree makes algorithm design easier. This project investigates the treewidth of road networks.
Learning Objectives:
Understand tree decomposition of graphs.
Able to implement an algorithm for constructing a tree decomposition of a given graph in almost linear time.
Able to optimize computer code for a faster running time.
Skills needed:
Familiarity with Python is desirable.