On labeled paths

by Wiegand, Nathan Michael, Ph.D., THE UNIVERSITY OF ALABAMA, 2010, 96 pages; 3409129


Labeled graph theory is the marriage of two common problem domains to computer science—graph theory and automata theory. Though each has been independently studied in depth, there has been little investigation of their intersection, the labeled paths.

This dissertation examines three results in the area of labeled path problems. The first result presents an empirical analysis of two context-free labeled all-pairs shortest-path algorithms using MapReduce as the experimental platform. The second and third results examine labeled paths in the context of formal languages beyond the context free languages. The second result is a lower bound on the length of the longest shortest path when the formal language constraining the path is a member of the control language hierarchy. Finally, the third result presents a labeled all-pairs shortest-path algorithm for each level of the infinite KLinear-Hierarchy.

AdviserRichard B. Borie
Source TypeDissertation
SubjectsComputer science
Publication Number3409129

About ProQuest Dissertations & Theses
With nearly 4 million records, the ProQuest Dissertations & Theses (PQDT) Global database is the most comprehensive collection of dissertations and theses in the world. It is the database of record for graduate research.

PQDT Global combines content from a range of the world's premier universities - from the Ivy League to the Russell Group. Of the nearly 4 million graduate works included in the database, ProQuest offers more than 2.5 million in full text formats. Of those, over 1.7 million are available in PDF format. More than 90,000 dissertations and theses are added to the database each year.

If you have questions, please feel free to visit the ProQuest Web site - http://www.proquest.com - or contact ProQuest Support.