Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Approximate Algorithm
Graph Algorithm
Intersection Graphs
Vertex Cover
Subscribe
Academic
Publications
Minimum Vertex Cover in Rectangle Graphs
Minimum Vertex Cover in Rectangle Graphs,10.1007/9783642157752_22,Computing Research Repository,Reuven BarYehuda,Danny Hermelin,Dror Rawitz
Edit
Minimum Vertex Cover in Rectangle Graphs
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Reuven BarYehuda
,
Danny Hermelin
,
Dror Rawitz
We consider the Minimum
Vertex Cover
problem in
intersection graphs
of axisparallel rectangles on the plane. We present two algorithms: The first is an EPTAS for noncrossing rectangle families, rectangle families R where R1 \ R2 is connected for every pair of rectangles R1, R2 2 R. The second algorithm achieves a factor of (1.5 + ") in general rectangle families, for any fixed " > 0, and works also for the weighted variant of the problem. Both algorithms exploit the plane properties of axisparallel rectangles in a nontrivial way.
Journal:
Computing Research Repository  CORR
, vol. abs/1001.3, pp. 255266, 2010
DOI:
10.1007/9783642157752_22
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
arxiv.org
)
(
www.informatik.unitrier.de
)
(
adsabs.harvard.edu
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
(
cs.haifa.ac.il
)
More »
Citation Context
(1)
...In fact, many recent works that solve optimization problems on rectangle intersection graphs have exploited this information in one way or another [
4
,11,8,23]...
Parinya Chalermsook
.
Coloring and Maximum Independent Set of Rectangles
References
(48)
Label placement by maximum independent set in rectangles
(
Citations: 98
)
Pankaj K. Agarwal
,
Marc J. Van Kreveld
,
Subhash Suri
Journal:
Computational Geometry: Theory and Applications  COMGEO
, vol. 11, no. 34, pp. 209218, 1998
New clique and independent set algorithms for circle graphs
(
Citations: 24
)
Alberto Apostolico
,
Mikhail J. Atallah
,
Susanne E. Hambrusch
Journal:
Discrete Applied Mathematics  DAM
, vol. 36, no. 1, pp. 124, 1992
Approximation algorithms for NPcomplete problems on planar graphs
(
Citations: 396
)
Brenda S. Baker
Journal:
Journal of The ACM  JACM
, vol. 41, no. 1, pp. 153180, 1994
A LinearTime Approximation Algorithm for the Weighted Vertex Cover Problem
(
Citations: 156
)
Reuven Baryehuda
,
Shimon Even
Journal:
Journal of Algorithms  JAL
, vol. 2, no. 2, pp. 198203, 1981
A localratio theorem for approximating the weighted vertex cover problem
(
Citations: 227
)
R. Baryehuda
,
S. Even
Published in 1985.
Sort by:
Citations
(1)
Coloring and Maximum Independent Set of Rectangles
Parinya Chalermsook