Home
Resource
Vertex cover in the sliding window model
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(272.38 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Nalam Venkata Subrahmanya, Sai Krishna Chaitanya. Vertex cover in the sliding window model. Retrieved from https://doi.org/doi:10.7282/t3-xyr3-1446

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleVertex cover in the sliding window model
NameNalam Venkata Subrahmanya, Sai Krishna Chaitanya (author); Assadi, Sepehr (chair); Bernstein, Aaron (member); Abello, James (member); Rutgers University; School of Graduate Studies
Date Created2021
Other Date2021-10 (degree)
SubjectComputer science, Sliding window model, Smooth histogram, Vertex cover
Extent1 online resource (vi, 36 pages) : illustrations
DescriptionWe study the problem of finding the minimum vertex cover for a graph in the sliding window model. The sliding window model is similar to the original streaming model where the edges of a graph whose vertices are known, arrive sequentially in a stream. However, in the sliding window model, only the graph induced by recent w edges of the stream is considered in computing the output. Therefore, when a new edge is arrived, the oldest edge would be deleted from the graph and not considered anymore in the computation of the output. Since we are only allowed to use o(w) space, all the recent w edges of the stream cannot be stored and we cannot explicitly find the edge that is getting deleted. This implicit deletion makes the sliding window model harder when compared to the original streaming model.
In this work, we observe that the (3 + ε)-approximation algorithm (ε ∈ (0, 1)) for maximum matching in the sliding window model can give a (6+O(ε))-approximation for the minimum vertex cover problem in the sliding window model. We give a counter example to the existing analysis of a (4 + ε)-approximation algorithm for the minimum vertex cover problem in the sliding window model and provide a correct analysis for the same algorithm. Finally, we come up with a (3 + ε)-approximation algorithm for the minimum vertex cover problem in the sliding window model using ̃O(n) space, where ∼ encompasses 1/ε,logn factors with n being the number of vertices in the graph.
NoteM.S.
NoteIncludes bibliographical references
Genretheses
Persistent URLhttps://doi.org/doi:10.7282/t3-xyr3-1446
LanguageEnglish
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