Repository logo
 

Two topics in combinatorial optimization: the domino portrait problem and the maximum clique problem

Simple item page
dc.contributor.authorAlshamary, Bader, author
dc.contributor.authorBetten, Anton, advisor
dc.date.accessioned2024-03-13T18:14:54Z
dc.date.available2024-03-13T18:14:54Z
dc.date.issued2007
dc.description.abstractCombinatorial Optimization plays a significant role in applied mathematics, supplying solutions to many scientific problems in a variety of fields, including computer science and computational networks. This dissertation first reviews a number of problems from combinatorial optimization and the algorithms used to solve them.
dc.description.abstractThe author then presents original solutions to the domino portrait problem, which involves arranging complete sets of dominos to resemble photographic portraits when seen from a distance. The first approach makes use of a greedy algorithm. Because the greedy algorithm often encounters blockages, a new technique was developed to avoid these blockages. Next, a local search algorithm was used to solve the problem. In both new solutions, the cost function was modified so that important positions in the portrait such as facial features were emphasized, thus improving the results. A singular value decomposition (SVD) was used to construct a "support matrix" necessary for this new cost function. Algorithms used in computing the SVD include the Householder method and the QR method.
dc.description.abstractThe second problem dealt with is the maximum clique problem and its application of finding ovoids in finite polar spaces. Again, local search provides an efficient way to search for maximum cliques in graphs and hence for finding ovoids in finite polar spaces.
dc.format.mediumborn digital
dc.format.mediumdoctoral dissertations
dc.identifierETDF_Alshamary_2007_3266398.pdf
dc.identifier.urihttps://hdl.handle.net/10217/237554
dc.languageEnglish
dc.language.isoeng
dc.publisherColorado State University. Libraries
dc.relation.ispartof2000-2019
dc.rightsCopyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright.
dc.rights.licensePer the terms of a contractual agreement, all use of this item is limited to the non-commercial use of Colorado State University and its authorized users.
dc.subjectdomino portrait problem
dc.subjectmaximum clique problem
dc.subjectmathematics
dc.titleTwo topics in combinatorial optimization: the domino portrait problem and the maximum clique problem
dc.typeText
dcterms.rights.dplaThis Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
thesis.degree.disciplineMathematics
thesis.degree.grantorColorado State University
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy (Ph.D.)

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ETDF_Alshamary_2007_3266398.pdf
Size:
4.32 MB
Format:
Adobe Portable Document Format
Download

Collections

2000-2019
Theses and Dissertations