Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for subject:(LOOP CUTSET). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Universiteit Utrecht

1. Timmer, S.T. Exact Algorithms for Loop Cutset.

Degree: 2012, Universiteit Utrecht

The LOOP CUTSET problem was historically posed by Pearl as a subroutine in Pearl’s algorithm for computing inference in probabilistic networks. The efficiency of the algorithm that solves the probabilistic inference highly depends on the size of the smallest known LOOP CUTSET. This justifies the search for exact algorithms for find- ing a minimum LOOP CUTSET. In this thesis we are investigating the algorithmic complexity of the problem. We will look at both the unparameterized problem and the problem parameterized by the treewidth of the input graph. For both we give an exact exponential time algorithm. The running times of these algorithms are O(1.7548n ) and O(4tw ) respectively, where tw is the treewidth of the input graph. Finally, we prove a lower bound of 3tw for the parameterized problem. Advisors/Committee Members: Bodlaender, H.L..

Subjects/Keywords: LOOP CUTSET; MAXIMUM INDUCED FOREST; Exact Algorithms; Treewidth; Cut & Count; Branch & Bound; Branch & Reduce; FEEDBACK VERTEX SET

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Timmer, S. T. (2012). Exact Algorithms for Loop Cutset. (Masters Thesis). Universiteit Utrecht. Retrieved from http://dspace.library.uu.nl:8080/handle/1874/253746

Chicago Manual of Style (16th Edition):

Timmer, S T. “Exact Algorithms for Loop Cutset.” 2012. Masters Thesis, Universiteit Utrecht. Accessed November 30, 2020. http://dspace.library.uu.nl:8080/handle/1874/253746.

MLA Handbook (7th Edition):

Timmer, S T. “Exact Algorithms for Loop Cutset.” 2012. Web. 30 Nov 2020.

Vancouver:

Timmer ST. Exact Algorithms for Loop Cutset. [Internet] [Masters thesis]. Universiteit Utrecht; 2012. [cited 2020 Nov 30]. Available from: http://dspace.library.uu.nl:8080/handle/1874/253746.

Council of Science Editors:

Timmer ST. Exact Algorithms for Loop Cutset. [Masters Thesis]. Universiteit Utrecht; 2012. Available from: http://dspace.library.uu.nl:8080/handle/1874/253746

.