Home
Resource
On the algorithmic aspects of Turán's Theorem
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(654.95 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Tsai, Meng-Tsung. On the algorithmic aspects of Turán's Theorem. Retrieved from https://doi.org/doi:10.7282/T3WS8XC7

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleOn the algorithmic aspects of Turán's Theorem
NameTsai, Meng-Tsung (author); Farach-Colton, Martin (chair); Rutgers University; School of Graduate Studies
Date Created2017
Other Date2017-10 (degree)
SubjectComputer Science
Extent1 online resource (v, 69 p. : ill.)
DescriptionTurán's Theorem gives an upper bound on the number of edges of n-node, K_r-free graphs, or equivalently it can be restated as that every n-node, m-edge graph has an independent set of size n^2/(n+2m). We illustrate how to apply Turán's Theorem to algorithmic problems in several ways. The complexity of dictionary operations, insertion for example, in external memory is well studied. However, the complexity of a batch of n operations is less known, and is seldom as easy as summing up the complexity of individual operations. We obtain lower bounds for batched predecessors by showing the necessity of fetching a set of information that preserves some "independence", where Turán's Theorem applies. We also prove lower bounds for batched deletions in cross-referenced dictionaries based on the existence of an adversarial input that forbids some patterns, where Turán's Theorem again applies. In addition, we present an interesting class of problems that are NP-hard to approximate. Turán’s theorem is useful in the proof that a large class of problems that can be defined in a simple framework are all NP-hard to approximate.
NotePh.D.
NoteIncludes bibliographical references
Noteby Meng-Tsung Tsai
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3WS8XC7
Languageeng
CollectionSchool of Graduate Studies Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024