1 resultado para Covering Number
em Repositório Institucional da Universidade de Aveiro - Portugal
Filtro por publicador
- ABACUS. Repositorio de Producción Científica - Universidad Europea (1)
- Aberdeen University (1)
- Aberystwyth University Repository - Reino Unido (4)
- Applied Math and Science Education Repository - Washington - USA (1)
- Aquatic Commons (158)
- Archive of European Integration (7)
- Archivo Digital para la Docencia y la Investigación - Repositorio Institucional de la Universidad del País Vasco (5)
- Avian Conservation and Ecology - Eletronic Cientific Hournal - Écologie et conservation des oiseaux: (2)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (BDPI/USP) (23)
- Biblioteca Digital de Teses e Dissertações Eletrônicas da UERJ (5)
- Boston University Digital Common (3)
- Brock University, Canada (11)
- Bulgarian Digital Mathematics Library at IMI-BAS (1)
- CaltechTHESIS (9)
- Cambridge University Engineering Department Publications Database (86)
- CentAUR: Central Archive University of Reading - UK (70)
- Center for Jewish History Digital Collections (2)
- Chinese Academy of Sciences Institutional Repositories Grid Portal (75)
- Cochin University of Science & Technology (CUSAT), India (8)
- Comissão Econômica para a América Latina e o Caribe (CEPAL) (1)
- CORA - Cork Open Research Archive - University College Cork - Ireland (3)
- CUNY Academic Works (3)
- Dalarna University College Electronic Archive (3)
- Deakin Research Online - Australia (54)
- Department of Computer Science E-Repository - King's College London, Strand, London (3)
- DI-fusion - The institutional repository of Université Libre de Bruxelles (6)
- Digital Archives@Colby (1)
- Diposit Digital de la UB - Universidade de Barcelona (3)
- Duke University (10)
- eResearch Archive - Queensland Department of Agriculture; Fisheries and Forestry (9)
- FUNDAJ - Fundação Joaquim Nabuco (1)
- Funes: Repositorio digital de documentos en Educación Matemática - Colombia (1)
- Greenwich Academic Literature Archive - UK (8)
- Helda - Digital Repository of University of Helsinki (18)
- Indian Institute of Science - Bangalore - Índia (88)
- Instituto Politécnico do Porto, Portugal (7)
- Ministerio de Cultura, Spain (8)
- Plymouth Marine Science Electronic Archive (PlyMSEA) (11)
- Publishing Network for Geoscientific & Environmental Data (1)
- QUB Research Portal - Research Directory and Institutional Repository for Queen's University Belfast (84)
- Queensland University of Technology - ePrints Archive (149)
- Repositório Científico do Instituto Politécnico de Lisboa - Portugal (1)
- Repositório Institucional da Universidade de Aveiro - Portugal (1)
- RUN (Repositório da Universidade Nova de Lisboa) - FCT (Faculdade de Cienecias e Technologia), Universidade Nova de Lisboa (UNL), Portugal (2)
- SAPIENTIA - Universidade do Algarve - Portugal (2)
- School of Medicine, Washington University, United States (8)
- Universidad del Rosario, Colombia (4)
- Universidade de Lisboa - Repositório Aberto (2)
- Universitat de Girona, Spain (2)
- Universitätsbibliothek Kassel, Universität Kassel, Germany (8)
- Université de Lausanne, Switzerland (6)
- Université de Montréal, Canada (12)
- University of Michigan (1)
- University of Queensland eSpace - Australia (1)
- University of Southampton, United Kingdom (3)
- University of Washington (1)
- WestminsterResearch - UK (1)
- Worcester Research and Publications - Worcester Research and Publications - UK (1)
Resumo:
A family of quadratic programming problems whose optimal values are upper bounds on the independence number of a graph is introduced. Among this family, the quadratic programming problem which gives the best upper bound is identified. Also the proof that the upper bound introduced by Hoffman and Lovász for regular graphs is a particular case of this family is given. In addition, some new results characterizing the class of graphs for which the independence number attains the optimal value of the above best upper bound are given. Finally a polynomial-time algorithm for approximating the size of the maximum independent set of an arbitrary graph is described and the computational experiments carried out on 36 DIMACS clique benchmark instances are reported.