Computation of Cycle Bases in Surface Embedded Graphs

Simple item page
dc.contributor.advisorFox, Kyle
dc.contributor.committeeMemberBereg, Sergey
dc.contributor.committeeMemberRaichel, Benjamin
dc.creatorStanley, Thomas
dc.date.accessioned2023-02-22T21:24:44Z
dc.date.available2023-02-22T21:24:44Z
dc.date.created2021-12
dc.date.issued2021-12-01T06:00:00.000Z
dc.date.submittedDecember 2021
dc.date.updated2023-02-22T21:24:45Z
dc.description.abstractWe study the problem of finding a cycle basis, a minimum weight set of independent cycles that form a basis of the cycle space for a given graph. We focus on finding the minimum cycle basis of directed graphs. This is a more complicated problem compared to the undirected case as the underlying field is Q for directed graphs instead of Z2 for undirected, which causes problems in the speed of calculations. Previously the fastest known deterministic algorithm to find the minimum cycle basis of a directed graph runs in O(m3n + m2n 2 log n) time [11]. We concentrate on graphs embedded on a surface of genus g. We modify algorithms for undirected graphs to work on directed graphs. We present an O(mn2 g 2 log g + mω+1) time algorithm to find the minimum cycle basis of a directed graph embedded on a surface of genus g. We also give an improvement on the minimum cycle basis in the undirected case
dc.format.mimetypeapplication/pdf
dc.identifier.uri
dc.identifier.urihttps://hdl.handle.net/10735.1/9622
dc.language.isoen
dc.subjectComputer Science
dc.titleComputation of Cycle Bases in Surface Embedded Graphs
dc.typeThesis
dc.type.materialtext
thesis.degree.collegeSchool of Engineering and Computer Science
thesis.degree.departmentComputer Science
thesis.degree.grantorThe University of Texas at Dallas
thesis.degree.nameMS

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
STANLEY-PRIMARY-2022-1.pdf
Size:
284.72 KB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
5.84 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description:
Download

Collections

UTD Theses and Dissertations