Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
Carroll, Stephen Accepted Thesis Carroll 07-25-13 su13.pdf (773.32 KB)
ETD Abstract Container
Abstract Header
Domain Specific Language for Dynamic Programming on Nice Tree Decompositions
Author Info
Carroll, Stephen P.
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1374762118
Abstract Details
Year and Degree
2013, Master of Science (MS), Ohio University, Computer Science (Engineering and Technology).
Abstract
In this thesis, we develop a Domain Specific Language (DSL) for a restricted class of algorithms that can be naturally parallelized given their base description. In particular, this thesis describes a DSL for dynamic programming algorithms on tree decompositions. These types of algorithms have been used successfully to provide efficient solutions to a number of NP-Complete problems on a restricted set of instances. These types of algorithms have a natural level of parallelism which can be exploited in order to expand the sizes and complexity of the NP-Hard inputs that can be handled via these techniques. Specifically, we analyze the classic NP-Complete problems of MAXIMUM INDEPENDENT SET (or MaxIS), MAXIMUM WEIGHTED INDEPENDENT SET (or MaxWIS), CLIQUE, and MINIMUM VERTEX COVER (or MinVC) using the developed DSL. In addition, this thesis provides a description of potential speedup using automatic parallelization in a C++ program that implements interpreting and compiling DSL files.
Committee
David Juedes (Advisor)
David Chelberg (Committee Member)
Drews Frank (Committee Member)
Sergio Lopez-Permouth (Committee Member)
Pages
148 p.
Subject Headings
Computer Science
Keywords
Domain Specific Language
;
DSL
;
Tree Decomposition
;
Dynamic Programming
;
DP
Recommended Citations
Refworks
EndNote
RIS
Mendeley
Citations
Carroll, S. P. (2013).
Domain Specific Language for Dynamic Programming on Nice Tree Decompositions
[Master's thesis, Ohio University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1374762118
APA Style (7th edition)
Carroll, Stephen.
Domain Specific Language for Dynamic Programming on Nice Tree Decompositions.
2013. Ohio University, Master's thesis.
OhioLINK Electronic Theses and Dissertations Center
, http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1374762118.
MLA Style (8th edition)
Carroll, Stephen. "Domain Specific Language for Dynamic Programming on Nice Tree Decompositions." Master's thesis, Ohio University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1374762118
Chicago Manual of Style (17th edition)
Abstract Footer
Document number:
ohiou1374762118
Download Count:
865
Copyright Info
© 2013, some rights reserved.
Domain Specific Language for Dynamic Programming on Nice Tree Decompositions by Stephen P. Carroll is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. Based on a work at etd.ohiolink.edu.
This open access ETD is published by Ohio University and OhioLINK.