
Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
| Metadados | Descrição | Idioma |
|---|---|---|
| Autor(es): dc.creator | Pereira, Dilson Lucas | - |
| Autor(es): dc.creator | Lucena, Abilio | - |
| Autor(es): dc.creator | Cunha, Alexandre Salles da | - |
| Autor(es): dc.creator | Simonetti, Luidi | - |
| Data de aceite: dc.date.accessioned | 2026-02-09T12:20:18Z | - |
| Data de disponibilização: dc.date.available | 2026-02-09T12:20:18Z | - |
| Data de envio: dc.date.issued | 2022-07-21 | - |
| Data de envio: dc.date.issued | 2022-07-21 | - |
| Data de envio: dc.date.issued | 2022-03 | - |
| Fonte completa do material: dc.identifier | https://repositorio.ufla.br/handle/1/50690 | - |
| Fonte completa do material: dc.identifier | https://doi.org/10.1287/ijoc.2022.1164 | - |
| Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/1159271 | - |
| Descrição: dc.description | A formulation, a heuristic, and branch-and-cut algorithms are investigated for the chordless cycle problem. This is the problem of finding a largest simple cycle for a given graph so that no edge between nonimmediately subsequent cycle vertices is contained in the graph. Leaving aside procedures based on complete enumeration, no previous exact solution algorithm appears to exist for the problem, which is relevant both in theoretical and practical terms. Extensive computational results are reported here for randomly generated graphs and for graphs originating from the literature. Under acceptable CPU times, certified optimal solutions are presented for graphs with as many as 100 vertices. Summary of Contribution: Finding chordless cycles of a graph, also known as holes, is relevant, among others, to graph theory, to the design of polyhedral based exact solution algorithms to integer programming (IP) problems, and to the practical applications that benefit from these algorithms. For instance, perfect graphs do not contain odd holes. Additionally, odd hole inequalities are valid for strengthening the formulations to numerous problems that are directly defined over graphs. Furthermore, these inequalites, in association with applicable conflict graphs, are used by all modern IP solvers to preprocess and strengthen virtually any IP formulation submitted to them. | - |
| Idioma: dc.language | en | - |
| Publicador: dc.publisher | Institute for Operations Research and the Management Sciences (INFORM) | - |
| Direitos: dc.rights | restrictAccess | - |
| ???dc.source???: dc.source | INFORMS Journal on Computing | - |
| Palavras-chave: dc.subject | Branch-and-cut algorithms | - |
| Palavras-chave: dc.subject | Heuristic | - |
| Palavras-chave: dc.subject | Chordless cycle | - |
| Palavras-chave: dc.subject | Induced subgraphs | - |
| Palavras-chave: dc.subject | Integer programming (IP) | - |
| Título: dc.title | Exact solution algorithms for the chordless cycle problem | - |
| Tipo de arquivo: dc.type | Artigo | - |
| Aparece nas coleções: | Repositório Institucional da Universidade Federal de Lavras (RIUFLA) | |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: