Geodesic
Additive approximation for edge-deletion problems
Noga Alon1 ; Asaf Shapira2 ; Benny Sudakov3
1Institute for Advanced Study<br/>Einstein Drive<br/>Princeton, NJ 08540<br/>United States
2School of Mathematics and College of Computing<br/>Georgia Institute of Technology<br/>Atlanta, GA 30332<br/>United States
3Department of Mathematics<br/>UCLA<br/>Box 951555<br/>Los Angeles, CA 90095<br/>United States
Annals of mathematics, Tome 170 (2009) no. 1, pp. 371-411
Cet article a éte moissonné depuis la source Annals of Mathematics website

Voir la notice de l'article

A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following algorithmic problem, called the edge-deletion problem; given a monotone property $\mathcal{P}$ and a graph $G$, compute the smallest number of edge deletions that are needed in order to turn $G$ into a graph satisfying $\mathcal{P}$. We denote this quantity by $E’_{\mathcal{P}}(G)$. The first result of this paper states that the edge-deletion problem can be efficiently approximated for any monotone property.

DOI : 10.4007/annals.2009.170.371

Noga Alon  1   ; Asaf Shapira  2   ; Benny Sudakov  3

1 Institute for Advanced Study<br/>Einstein Drive<br/>Princeton, NJ 08540<br/>United States
2 School of Mathematics and College of Computing<br/>Georgia Institute of Technology<br/>Atlanta, GA 30332<br/>United States
3 Department of Mathematics<br/>UCLA<br/>Box 951555<br/>Los Angeles, CA 90095<br/>United States 
@article{10_4007_annals_2009_170_371,
     author = {Noga Alon and Asaf Shapira and Benny Sudakov},
     title = {Additive approximation for edge-deletion problems},
     journal = {Annals of mathematics},
     pages = {371--411},
     year = {2009},
     volume = {170},
     number = {1},
     doi = {10.4007/annals.2009.170.371},
     mrnumber = {2521119},
     zbl = {1185.05132},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4007/annals.2009.170.371/}
}
TY  - JOUR
AU  - Noga Alon
AU  - Asaf Shapira
AU  - Benny Sudakov
TI  - Additive approximation for edge-deletion problems
JO  - Annals of mathematics
PY  - 2009
SP  - 371
EP  - 411
VL  - 170
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4007/annals.2009.170.371/
DO  - 10.4007/annals.2009.170.371
LA  - en
ID  - 10_4007_annals_2009_170_371
ER  - 
%0 Journal Article
%A Noga Alon
%A Asaf Shapira
%A Benny Sudakov
%T Additive approximation for edge-deletion problems
%J Annals of mathematics
%D 2009
%P 371-411
%V 170
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4007/annals.2009.170.371/
%R 10.4007/annals.2009.170.371
%G en
%F 10_4007_annals_2009_170_371
Noga Alon; Asaf Shapira; Benny Sudakov. Additive approximation for edge-deletion problems. Annals of mathematics, Tome 170 (2009) no. 1, pp. 371-411. doi: 10.4007/annals.2009.170.371

Cité par Sources :