Show simple item record

dc.contributor.advisorChen, Jianer
dc.creatorCao, Yixin
dc.date.accessioned2012-07-16T15:58:42Z
dc.date.accessioned2012-07-16T20:25:17Z
dc.date.available2012-07-16T15:58:42Z
dc.date.available2012-07-16T20:25:17Z
dc.date.created2012-05
dc.date.issued2012-07-16
dc.date.submittedMay 2012
dc.identifier.urihttp://hdl.handle.net/1969.1/ETD-TAMU-2012-05-11160
dc.description.abstractClustering is the unsupervised classification of patterns into groups, which is easy provided the data of patterns are consistent. However, real data are almost always tempered with inconsistencies, which make it a hard problem, and actually, the most widely studied formulations, correlation clustering and hierarchical clustering, are both NP-hard. In the graph representation of data, inconsistencies also frequently present themselves as cycles, also called deadlocks, and to break cycles by removing vertices is the objective of the classical feedback vertex set (FVS) problem. This dissertation studies the three problems, correlation clustering, hierarchical clustering, and disjoint-FVS (a variation of FVS), from a kernelization approach. A kernelization algorithm in polynomial time reduces a problem instance provably to speed up the further processing with other approaches. For each of the problems studied, an efficient kernelization algorithm of linear or sub-quadratic running time is presented. All the kernels obtained in this dissertation have linear size with very small constants. Better parameterized algorithms are also designed based on the kernels for the last two problems. Finally, some concluding remarks on possible directions for future research are briefly mentioned.en
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.subjectkernelizationen
dc.subjectclusteringen
dc.subjectfeedback vertex seten
dc.subjectfvsen
dc.titleClustering and Inconsistent Information: A Kernelization Approachen
dc.typeThesisen
thesis.degree.departmentComputer Science and Engineeringen
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorTexas A&M Universityen
thesis.degree.nameDoctor of Philosophyen
thesis.degree.levelDoctoralen
dc.contributor.committeeMemberButenko, Sergiy
dc.contributor.committeeMemberFriesen, Donald K.
dc.contributor.committeeMemberWilliams, Tiffani
dc.type.genrethesisen
dc.type.materialtexten


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record