Neural Network Models for the Maximum Clique Problem
ABSTRACT: In this paper we describe two neural network based algorithms for the Maximum Clique Problem. The developed algorithms provide discrete and continuos descent dynamics respectively to approximate the solution of the quadratic 0-1 formulation of the Maximum Clique Problem. The discrete appro...
- Autores:
-
López Reyes, Nancy
Cruz Rodés, Roberto
- Tipo de recurso:
- Article of investigation
- Fecha de publicación:
- 2000
- Institución:
- Universidad de Antioquia
- Repositorio:
- Repositorio UdeA
- Idioma:
- eng
- OAI Identifier:
- oai:bibliotecadigital.udea.edu.co:10495/34430
- Acceso en línea:
- https://hdl.handle.net/10495/34430
- Palabra clave:
- Heurística
Heuristics
Redes Neurales de la Computación
Neural Networks, Computer
Optimización combinatoria
Combinatorial optimization
Teoría de función geométrica
Geometric function theory
Problema del clique máximo
Problema cuadrático 0-1
https://id.nlm.nih.gov/mesh/D000066506
https://id.nlm.nih.gov/mesh/D016571
- Rights
- openAccess
- License
- https://creativecommons.org/licenses/by-nc-nd/4.0/
| id |
UDEA2_9f44bd8b9dbd2e514cf7c2a3302c1acf |
|---|---|
| oai_identifier_str |
oai:bibliotecadigital.udea.edu.co:10495/34430 |
| network_acronym_str |
UDEA2 |
| network_name_str |
Repositorio UdeA |
| repository_id_str |
|
| dc.title.spa.fl_str_mv |
Neural Network Models for the Maximum Clique Problem |
| title |
Neural Network Models for the Maximum Clique Problem |
| spellingShingle |
Neural Network Models for the Maximum Clique Problem Heurística Heuristics Redes Neurales de la Computación Neural Networks, Computer Optimización combinatoria Combinatorial optimization Teoría de función geométrica Geometric function theory Problema del clique máximo Problema cuadrático 0-1 https://id.nlm.nih.gov/mesh/D000066506 https://id.nlm.nih.gov/mesh/D016571 |
| title_short |
Neural Network Models for the Maximum Clique Problem |
| title_full |
Neural Network Models for the Maximum Clique Problem |
| title_fullStr |
Neural Network Models for the Maximum Clique Problem |
| title_full_unstemmed |
Neural Network Models for the Maximum Clique Problem |
| title_sort |
Neural Network Models for the Maximum Clique Problem |
| dc.creator.fl_str_mv |
López Reyes, Nancy Cruz Rodés, Roberto |
| dc.contributor.author.none.fl_str_mv |
López Reyes, Nancy Cruz Rodés, Roberto |
| dc.contributor.researchgroup.spa.fl_str_mv |
Modelación con Ecuaciones Diferenciales |
| dc.subject.decs.none.fl_str_mv |
Heurística Heuristics Redes Neurales de la Computación Neural Networks, Computer |
| topic |
Heurística Heuristics Redes Neurales de la Computación Neural Networks, Computer Optimización combinatoria Combinatorial optimization Teoría de función geométrica Geometric function theory Problema del clique máximo Problema cuadrático 0-1 https://id.nlm.nih.gov/mesh/D000066506 https://id.nlm.nih.gov/mesh/D016571 |
| dc.subject.lemb.none.fl_str_mv |
Optimización combinatoria Combinatorial optimization Teoría de función geométrica Geometric function theory |
| dc.subject.proposal.spa.fl_str_mv |
Problema del clique máximo Problema cuadrático 0-1 |
| dc.subject.meshuri.none.fl_str_mv |
https://id.nlm.nih.gov/mesh/D000066506 https://id.nlm.nih.gov/mesh/D016571 |
| description |
ABSTRACT: In this paper we describe two neural network based algorithms for the Maximum Clique Problem. The developed algorithms provide discrete and continuos descent dynamics respectively to approximate the solution of the quadratic 0-1 formulation of the Maximum Clique Problem. The discrete approach performed better, maintaining computational competitiveness to greedy randomized search procedures. Experimental results on test graphs of size up to 3361 vertices and 5506380 edges are presented. |
| publishDate |
2000 |
| dc.date.issued.none.fl_str_mv |
2000 |
| dc.date.accessioned.none.fl_str_mv |
2023-04-02T14:39:27Z |
| dc.date.available.none.fl_str_mv |
2023-04-02T14:39:27Z |
| dc.type.spa.fl_str_mv |
Artículo de investigación |
| dc.type.coar.spa.fl_str_mv |
http://purl.org/coar/resource_type/c_2df8fbb1 |
| dc.type.redcol.spa.fl_str_mv |
https://purl.org/redcol/resource_type/ART |
| dc.type.coarversion.spa.fl_str_mv |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| dc.type.driver.spa.fl_str_mv |
info:eu-repo/semantics/article |
| dc.type.version.spa.fl_str_mv |
info:eu-repo/semantics/publishedVersion |
| format |
http://purl.org/coar/resource_type/c_2df8fbb1 |
| status_str |
publishedVersion |
| dc.identifier.issn.none.fl_str_mv |
0257-4306 |
| dc.identifier.uri.none.fl_str_mv |
https://hdl.handle.net/10495/34430 |
| dc.identifier.eissn.none.fl_str_mv |
2224-5405 |
| identifier_str_mv |
0257-4306 2224-5405 |
| url |
https://hdl.handle.net/10495/34430 |
| dc.language.iso.spa.fl_str_mv |
eng |
| language |
eng |
| dc.relation.citationendpage.spa.fl_str_mv |
112 |
| dc.relation.citationissue.spa.fl_str_mv |
2 |
| dc.relation.citationstartpage.spa.fl_str_mv |
103 |
| dc.relation.citationvolume.spa.fl_str_mv |
21 |
| dc.relation.ispartofjournal.spa.fl_str_mv |
Investigacion Operacional |
| dc.rights.uri.spa.fl_str_mv |
https://creativecommons.org/licenses/by-nc-nd/4.0/ |
| dc.rights.uri.*.fl_str_mv |
http://creativecommons.org/licenses/by-nc-nd/2.5/co/ |
| dc.rights.accessrights.spa.fl_str_mv |
info:eu-repo/semantics/openAccess |
| dc.rights.coar.spa.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
| rights_invalid_str_mv |
https://creativecommons.org/licenses/by-nc-nd/4.0/ http://creativecommons.org/licenses/by-nc-nd/2.5/co/ http://purl.org/coar/access_right/c_abf2 |
| eu_rights_str_mv |
openAccess |
| dc.format.extent.spa.fl_str_mv |
10 |
| dc.format.mimetype.spa.fl_str_mv |
application/pdf |
| dc.publisher.spa.fl_str_mv |
Ministerio de Educación Superior; Universidad de La Habana, Facultad de Matemática y Computación, Departamento de Matemática Aplicada |
| dc.publisher.place.spa.fl_str_mv |
Ciudad de la Habana, Cuba |
| institution |
Universidad de Antioquia |
| bitstream.url.fl_str_mv |
https://bibliotecadigital.udea.edu.co/bitstreams/2c6e227b-c5b4-4cd1-8e82-4a8e368ed7cf/download https://bibliotecadigital.udea.edu.co/bitstreams/39f8a59d-eb2b-47f9-aecf-6cc96382c8e1/download https://bibliotecadigital.udea.edu.co/bitstreams/cea24b8f-279a-43dc-a173-9b3e3d5da882/download https://bibliotecadigital.udea.edu.co/bitstreams/e2258d2f-a312-4f93-823c-20c28579bbfc/download https://bibliotecadigital.udea.edu.co/bitstreams/767137e5-9695-48dc-8501-8efac43181be/download |
| bitstream.checksum.fl_str_mv |
2dc053fae515a94ca7a09f805c9aa8b9 b88b088d9957e670ce3b3fbe2eedbc13 8a4605be74aa9ea9d79846c1fba20a33 76508de7510bb5940aa22acbb724b1c6 572c7c82b802623ff62fd4d956d00b5a |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 MD5 MD5 MD5 |
| repository.name.fl_str_mv |
Repositorio Institucional de la Universidad de Antioquia |
| repository.mail.fl_str_mv |
aplicacionbibliotecadigitalbiblioteca@udea.edu.co |
| _version_ |
1851052208300228608 |
| spelling |
López Reyes, NancyCruz Rodés, RobertoModelación con Ecuaciones Diferenciales2023-04-02T14:39:27Z2023-04-02T14:39:27Z20000257-4306https://hdl.handle.net/10495/344302224-5405ABSTRACT: In this paper we describe two neural network based algorithms for the Maximum Clique Problem. The developed algorithms provide discrete and continuos descent dynamics respectively to approximate the solution of the quadratic 0-1 formulation of the Maximum Clique Problem. The discrete approach performed better, maintaining computational competitiveness to greedy randomized search procedures. Experimental results on test graphs of size up to 3361 vertices and 5506380 edges are presented.RESUMEN: Se describen dos algoritmos basados en redes neuronales para el Problema del Clique Máximo de un grafo. Los algoritmos desarrollados implementan dinámicas descendentes, en un caso continua y en el otro discreta, para aproximar la solución del problema planteado a partir de la formulación cuadrática del mismo. El algoritmo discreto presenta un mejor desempeño, alcanzando resultados similares a los obtenidos con otras heurísticas. Se discuten los resultados de la aplicación de los algoritmos en un conjunto de grafos de hasta 3361 vértices y 5506380 aristas.COL002436510application/pdfengMinisterio de Educación Superior; Universidad de La Habana, Facultad de Matemática y Computación, Departamento de Matemática AplicadaCiudad de la Habana, Cubahttps://creativecommons.org/licenses/by-nc-nd/4.0/http://creativecommons.org/licenses/by-nc-nd/2.5/co/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Neural Network Models for the Maximum Clique ProblemArtículo de investigaciónhttp://purl.org/coar/resource_type/c_2df8fbb1https://purl.org/redcol/resource_type/ARThttp://purl.org/coar/version/c_970fb48d4fbd8a85info:eu-repo/semantics/articleinfo:eu-repo/semantics/publishedVersionHeurísticaHeuristicsRedes Neurales de la ComputaciónNeural Networks, ComputerOptimización combinatoriaCombinatorial optimizationTeoría de función geométricaGeometric function theoryProblema del clique máximoProblema cuadrático 0-1https://id.nlm.nih.gov/mesh/D000066506https://id.nlm.nih.gov/mesh/D016571112210321Investigacion OperacionalPublicationORIGINALLopezNancy_2000_NeuralNetworkModels.pdfLopezNancy_2000_NeuralNetworkModels.pdfArtículo de investigaciónapplication/pdf150824https://bibliotecadigital.udea.edu.co/bitstreams/2c6e227b-c5b4-4cd1-8e82-4a8e368ed7cf/download2dc053fae515a94ca7a09f805c9aa8b9MD51trueAnonymousREADCC-LICENSElicense_rdflicense_rdfapplication/rdf+xml; charset=utf-8823https://bibliotecadigital.udea.edu.co/bitstreams/39f8a59d-eb2b-47f9-aecf-6cc96382c8e1/downloadb88b088d9957e670ce3b3fbe2eedbc13MD52falseAnonymousREADLICENSElicense.txtlicense.txttext/plain; charset=utf-81748https://bibliotecadigital.udea.edu.co/bitstreams/cea24b8f-279a-43dc-a173-9b3e3d5da882/download8a4605be74aa9ea9d79846c1fba20a33MD53falseAnonymousREADTEXTLopezNancy_2000_NeuralNetworkModels.pdf.txtLopezNancy_2000_NeuralNetworkModels.pdf.txtExtracted texttext/plain31032https://bibliotecadigital.udea.edu.co/bitstreams/e2258d2f-a312-4f93-823c-20c28579bbfc/download76508de7510bb5940aa22acbb724b1c6MD54falseAnonymousREADTHUMBNAILLopezNancy_2000_NeuralNetworkModels.pdf.jpgLopezNancy_2000_NeuralNetworkModels.pdf.jpgGenerated Thumbnailimage/jpeg12976https://bibliotecadigital.udea.edu.co/bitstreams/767137e5-9695-48dc-8501-8efac43181be/download572c7c82b802623ff62fd4d956d00b5aMD55falseAnonymousREAD10495/34430oai:bibliotecadigital.udea.edu.co:10495/344302025-03-26 18:38:28.326https://creativecommons.org/licenses/by-nc-nd/4.0/open.accesshttps://bibliotecadigital.udea.edu.coRepositorio Institucional de la Universidad de Antioquiaaplicacionbibliotecadigitalbiblioteca@udea.edu.coTk9URTogUExBQ0UgWU9VUiBPV04gTElDRU5TRSBIRVJFClRoaXMgc2FtcGxlIGxpY2Vuc2UgaXMgcHJvdmlkZWQgZm9yIGluZm9ybWF0aW9uYWwgcHVycG9zZXMgb25seS4KCk5PTi1FWENMVVNJVkUgRElTVFJJQlVUSU9OIExJQ0VOU0UKCkJ5IHNpZ25pbmcgYW5kIHN1Ym1pdHRpbmcgdGhpcyBsaWNlbnNlLCB5b3UgKHRoZSBhdXRob3Iocykgb3IgY29weXJpZ2h0Cm93bmVyKSBncmFudHMgdG8gRFNwYWNlIFVuaXZlcnNpdHkgKERTVSkgdGhlIG5vbi1leGNsdXNpdmUgcmlnaHQgdG8gcmVwcm9kdWNlLAp0cmFuc2xhdGUgKGFzIGRlZmluZWQgYmVsb3cpLCBhbmQvb3IgZGlzdHJpYnV0ZSB5b3VyIHN1Ym1pc3Npb24gKGluY2x1ZGluZwp0aGUgYWJzdHJhY3QpIHdvcmxkd2lkZSBpbiBwcmludCBhbmQgZWxlY3Ryb25pYyBmb3JtYXQgYW5kIGluIGFueSBtZWRpdW0sCmluY2x1ZGluZyBidXQgbm90IGxpbWl0ZWQgdG8gYXVkaW8gb3IgdmlkZW8uCgpZb3UgYWdyZWUgdGhhdCBEU1UgbWF5LCB3aXRob3V0IGNoYW5naW5nIHRoZSBjb250ZW50LCB0cmFuc2xhdGUgdGhlCnN1Ym1pc3Npb24gdG8gYW55IG1lZGl1bSBvciBmb3JtYXQgZm9yIHRoZSBwdXJwb3NlIG9mIHByZXNlcnZhdGlvbi4KCllvdSBhbHNvIGFncmVlIHRoYXQgRFNVIG1heSBrZWVwIG1vcmUgdGhhbiBvbmUgY29weSBvZiB0aGlzIHN1Ym1pc3Npb24gZm9yCnB1cnBvc2VzIG9mIHNlY3VyaXR5LCBiYWNrLXVwIGFuZCBwcmVzZXJ2YXRpb24uCgpZb3UgcmVwcmVzZW50IHRoYXQgdGhlIHN1Ym1pc3Npb24gaXMgeW91ciBvcmlnaW5hbCB3b3JrLCBhbmQgdGhhdCB5b3UgaGF2ZQp0aGUgcmlnaHQgdG8gZ3JhbnQgdGhlIHJpZ2h0cyBjb250YWluZWQgaW4gdGhpcyBsaWNlbnNlLiBZb3UgYWxzbyByZXByZXNlbnQKdGhhdCB5b3VyIHN1Ym1pc3Npb24gZG9lcyBub3QsIHRvIHRoZSBiZXN0IG9mIHlvdXIga25vd2xlZGdlLCBpbmZyaW5nZSB1cG9uCmFueW9uZSdzIGNvcHlyaWdodC4KCklmIHRoZSBzdWJtaXNzaW9uIGNvbnRhaW5zIG1hdGVyaWFsIGZvciB3aGljaCB5b3UgZG8gbm90IGhvbGQgY29weXJpZ2h0LAp5b3UgcmVwcmVzZW50IHRoYXQgeW91IGhhdmUgb2J0YWluZWQgdGhlIHVucmVzdHJpY3RlZCBwZXJtaXNzaW9uIG9mIHRoZQpjb3B5cmlnaHQgb3duZXIgdG8gZ3JhbnQgRFNVIHRoZSByaWdodHMgcmVxdWlyZWQgYnkgdGhpcyBsaWNlbnNlLCBhbmQgdGhhdApzdWNoIHRoaXJkLXBhcnR5IG93bmVkIG1hdGVyaWFsIGlzIGNsZWFybHkgaWRlbnRpZmllZCBhbmQgYWNrbm93bGVkZ2VkCndpdGhpbiB0aGUgdGV4dCBvciBjb250ZW50IG9mIHRoZSBzdWJtaXNzaW9uLgoKSUYgVEhFIFNVQk1JU1NJT04gSVMgQkFTRUQgVVBPTiBXT1JLIFRIQVQgSEFTIEJFRU4gU1BPTlNPUkVEIE9SIFNVUFBPUlRFRApCWSBBTiBBR0VOQ1kgT1IgT1JHQU5JWkFUSU9OIE9USEVSIFRIQU4gRFNVLCBZT1UgUkVQUkVTRU5UIFRIQVQgWU9VIEhBVkUKRlVMRklMTEVEIEFOWSBSSUdIVCBPRiBSRVZJRVcgT1IgT1RIRVIgT0JMSUdBVElPTlMgUkVRVUlSRUQgQlkgU1VDSApDT05UUkFDVCBPUiBBR1JFRU1FTlQuCgpEU1Ugd2lsbCBjbGVhcmx5IGlkZW50aWZ5IHlvdXIgbmFtZShzKSBhcyB0aGUgYXV0aG9yKHMpIG9yIG93bmVyKHMpIG9mIHRoZQpzdWJtaXNzaW9uLCBhbmQgd2lsbCBub3QgbWFrZSBhbnkgYWx0ZXJhdGlvbiwgb3RoZXIgdGhhbiBhcyBhbGxvd2VkIGJ5IHRoaXMKbGljZW5zZSwgdG8geW91ciBzdWJtaXNzaW9uLgo= |