Dissertation
Simplicial Complexes and the Optimal Homologous Chain Problem
Doctor of Philosophy (PhD), Washington State University
01/2013
Handle:
https://hdl.handle.net/2376/4755
Abstract
This dissertation examines topological properties of a finite simplicial complex K that ensure any Optimal Homologous Chain Problem with an arbitrary p-dimensional chain as input can be solved in polynomial time. One such property already known is when the (p+1)-boundary matrix of K is totally unimodular. This dissertation defines a weaker but related condition for K called NTU-neutralized, and shows this also ensures polynomial time for any OHCP with an arbitrary p-chain input. This is done by defining OCHP over the reals or rationals instead of integers, and formulating the OHCP as an LP. Several properties of basic solutions and vertices of an OCHP LP are also revealed.
This dissertation also studies edge contractions on a finite simplicial complex K, a common operation to simplify complexes. It defines the p-link condition for an edge ab in K. We show that if ab satisfies the p-link condition, and the (p+1)-boundary matrix of K is totally unimodular, then the (p+1)-boundary martix of the remaining complex after contracting ab is also totally unimodular.
Metrics
5 File views/ downloads
6 Record Views
Details
- Title
- Simplicial Complexes and the Optimal Homologous Chain Problem
- Creators
- Gavin W. Smith
- Contributors
- Bala Krishnamoorthy (Advisor)Matt Hudelson (Committee Member)K. A. Ariyawansa (Committee Member)
- Awarding Institution
- Washington State University
- Academic Unit
- Mathematics and Statistics, Department of
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Number of pages
- 78
- Identifiers
- 99900581744501842
- Language
- English
- Resource Type
- Dissertation