1 resultado para Tail-approximation
em Boston University Digital Common
Filtro por publicador
- KUPS-Datenbank - Universität zu Köln - Kölner UniversitätsPublikationsServer (1)
- ABACUS. Repositorio de Producción Científica - Universidad Europea (1)
- Aberdeen University (1)
- Aberystwyth University Repository - Reino Unido (3)
- Academic Archive On-line (Karlstad University; Sweden) (1)
- AMS Tesi di Dottorato - Alm@DL - Università di Bologna (1)
- AMS Tesi di Laurea - Alm@DL - Università di Bologna (1)
- Aquatic Commons (7)
- ArchiMeD - Elektronische Publikationen der Universität Mainz - Alemanha (2)
- Archive of European Integration (189)
- Aston University Research Archive (14)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (8)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (BDPI/USP) (12)
- Biodiversity Heritage Library, United States (3)
- BORIS: Bern Open Repository and Information System - Berna - Suiça (42)
- Boston University Digital Common (1)
- Brock University, Canada (4)
- Bucknell University Digital Commons - Pensilvania - USA (2)
- Bulgarian Digital Mathematics Library at IMI-BAS (21)
- CaltechTHESIS (5)
- Cambridge University Engineering Department Publications Database (63)
- CentAUR: Central Archive University of Reading - UK (38)
- Chinese Academy of Sciences Institutional Repositories Grid Portal (39)
- Cochin University of Science & Technology (CUSAT), India (6)
- Comissão Econômica para a América Latina e o Caribe (CEPAL) (1)
- CORA - Cork Open Research Archive - University College Cork - Ireland (1)
- Corvinus Research Archive - The institutional repository for the Corvinus University of Budapest (1)
- CUNY Academic Works (3)
- Deakin Research Online - Australia (24)
- Department of Computer Science E-Repository - King's College London, Strand, London (6)
- DI-fusion - The institutional repository of Université Libre de Bruxelles (1)
- Digital Commons - Michigan Tech (2)
- Digital Commons at Florida International University (4)
- Digital Peer Publishing (1)
- DigitalCommons@The Texas Medical Center (6)
- DigitalCommons@University of Nebraska - Lincoln (1)
- Diposit Digital de la UB - Universidade de Barcelona (5)
- DRUM (Digital Repository at the University of Maryland) (1)
- Duke University (5)
- eResearch Archive - Queensland Department of Agriculture; Fisheries and Forestry (2)
- Greenwich Academic Literature Archive - UK (10)
- Helda - Digital Repository of University of Helsinki (9)
- Illinois Digital Environment for Access to Learning and Scholarship Repository (1)
- Indian Institute of Science - Bangalore - Índia (69)
- Instituto Gulbenkian de Ciência (1)
- Instituto Politécnico do Porto, Portugal (1)
- Lume - Repositório Digital da Universidade Federal do Rio Grande do Sul (1)
- Massachusetts Institute of Technology (6)
- Memorial University Research Repository (1)
- Ministerio de Cultura, Spain (2)
- National Center for Biotechnology Information - NCBI (21)
- Nottingham eTheses (1)
- Plymouth Marine Science Electronic Archive (PlyMSEA) (1)
- Publishing Network for Geoscientific & Environmental Data (4)
- QUB Research Portal - Research Directory and Institutional Repository for Queen's University Belfast (69)
- Queensland University of Technology - ePrints Archive (44)
- Repositorio Académico de la Universidad Nacional de Costa Rica (1)
- Repositório digital da Fundação Getúlio Vargas - FGV (4)
- Repositório Digital da UNIVERSIDADE DA MADEIRA - Portugal (1)
- Repositorio Institucional de la Universidad de Málaga (1)
- Repositório Institucional UNESP - Universidade Estadual Paulista "Julio de Mesquita Filho" (40)
- RUN (Repositório da Universidade Nova de Lisboa) - FCT (Faculdade de Cienecias e Technologia), Universidade Nova de Lisboa (UNL), Portugal (1)
- School of Medicine, Washington University, United States (2)
- Universidad de Alicante (3)
- Universidad del Rosario, Colombia (3)
- Universidad Politécnica de Madrid (12)
- Universidade Complutense de Madrid (1)
- Universidade Federal do Pará (2)
- Universitat de Girona, Spain (3)
- Universitätsbibliothek Kassel, Universität Kassel, Germany (4)
- Université de Montréal (3)
- Université de Montréal, Canada (12)
- University of Michigan (18)
- University of Queensland eSpace - Australia (15)
- WestminsterResearch - UK (1)
Resumo:
The performance of a randomized version of the subgraph-exclusion algorithm (called Ramsey) for CLIQUE by Boppana and Halldorsson is studied on very large graphs. We compare the performance of this algorithm with the performance of two common heuristic algorithms, the greedy heuristic and a version of simulated annealing. These algorithms are tested on graphs with up to 10,000 vertices on a workstation and graphs as large as 70,000 vertices on a Connection Machine. Our implementations establish the ability to run clique approximation algorithms on very large graphs. We test our implementations on a variety of different graphs. Our conclusions indicate that on randomly generated graphs minor changes to the distribution can cause dramatic changes in the performance of the heuristic algorithms. The Ramsey algorithm, while not as good as the others for the most common distributions, seems more robust and provides a more even overall performance. In general, and especially on deterministically generated graphs, a combination of simulated annealing with either the Ramsey algorithm or the greedy heuristic seems to perform best. This combined algorithm works particularly well on large Keller and Hamming graphs and has a competitive overall performance on the DIMACS benchmark graphs.