Inicio Nosotros Búsquedas
Buscar en nuestra Base de Datos:     
Palabras claves o descriptores: APX-COMPLETE (Comienzo)
Sólo un registro cumplió la condición especificada en la base de información bciucla.
Publicación seriada
Referencias AnalíticasReferencias Analíticas
Autor: Monnot, Jérôme monnot@lamsade.dauphine.fr <monnot@lamsade.dauphine.fr> Oprima aquí para enviar un correo electrónico a esta dirección ; Paschos, Vangelis Th. paschos@lamsade.dauphine.fr <paschos@lamsade.dauphine.fr> Oprima aquí para enviar un correo electrónico a esta dirección; Toulouse, Sophie toulouse@lamsade.dauphine.fr <toulouse@lamsade.dauphine.fr> Oprima aquí para enviar un correo electrónico a esta dirección
Título: Local approximations for maximum partial subgraph problem
Páginas/Colación: pp. 217-224
Url: Ir a http://www.sciencedirect.com/science/journal/01676377http://www.sciencedirect.com/science/journal/01676377
Operations Research Letters Vol. 32, no. 3 Mayo 2004
Información de existenciaInformación de existencia

Palabras Claves: Palabras: APPROXIMATION ALGORITHMS APPROXIMATION ALGORITHMS, Palabras: APX-COMPLETE APX-COMPLETE, Palabras: HEREDITARY PROPERTY HEREDITARY PROPERTY, Palabras: LOCAL SEARCH LOCAL SEARCH, Palabras: MAXIMUM SUBGRAPH PROBLEM MAXIMUM SUBGRAPH PROBLEM, Palabras: MINIMUM VERTEX DELETION PROBLEM MINIMUM VERTEX DELETION PROBLEM

Resumen
We deal with Max H0-Free Partial Subgraph. We mainly prove that 3-locally optimum solutions achieve approximation ratio (d0+1)/(B+2+v0), where B=maxvVdG(v), d0=minvV(H0)dH0(v) and ?0=(|V(H0)|+1)/d0. Next, we show that this ratio rises up to 3/(B+1) when H0=K3. Finally, we provide hardness results for K3-Free Partial Subgraph.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno

Generados por el servidor 'bibcyt.ucla.edu.ve' (3.148.113.8)
Adaptive Server Anywhere (07.00.0000)
ODBC
Sesión="" Sesión anterior=""
 ejecutando Back-end Alejandría BE 7.0.7b0 ** * *
3.148.113.8 (NTM) bajo el ambiente Apache/2.2.4 (Win32) PHP/5.2.2.
usando una conexión ODBC (RowCount) al manejador de bases de datos..
Versión de la base de información bciucla: 7.0.0 (con listas invertidas [2.0])

Cliente: 3.148.113.8
Salida con Javascript
** Back-end Alejandría BE 7.0.7b0 *