| 1. Identificação | |
| Tipo de Referência | Artigo em Revista Científica (Journal Article) |
| Site | mtc-m16d.sid.inpe.br |
| Código do Detentor | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S |
| Identificador | 8JMKD3MGP7W/37JUAGE |
| Repositório | sid.inpe.br/mtc-m19@80/2010/06.01.19.41 (acesso restrito) |
| Última Atualização | 2010:07.14.17.54.36 (UTC) administrator |
| Repositório de Metadados | sid.inpe.br/mtc-m19@80/2010/06.01.19.41.10 |
| Última Atualização dos Metadados | 2018:06.05.04.36.44 (UTC) administrator |
| Chave Secundária | INPE--PRE/ |
| DOI | 10.1007/s12351-009-0075-1 |
| ISSN | 1866-1505 |
| Chave de Citação | RibeiroMaurLore:2010:LaDeMa |
| Título | A lagrangean decomposition for the maximum independent set problem applied to map labeling  |
| Ano | 2010 |
| Data de Acesso | 19 maio 2024 |
| Tipo Secundário | PRE PI |
| Número de Arquivos | 1 |
| Tamanho | 647 KiB |
| 2. Contextualização | |
| Autor | 1 Ribeiro, G. M. 2 Mauri, G. R. 3 Lorena, L. Antonio Nogueira |
| Grupo | 1 LAC-CTE-INPE-MCT-BR |
| Afiliação | 1 Universidade Federal do Espírito Santo 2 Universidade Federal do Espírito Santo 3 Instituto Nacional de Pesquisas Espaciais (INPE) |
| Revista | Operational Research |
| Volume | In press |
| Histórico (UTC) | 2010-07-05 14:54:47 :: simone -> marciana :: 2010 2011-09-19 16:16:56 :: marciana -> administrator :: 2010 2018-06-05 04:36:44 :: administrator -> marciana :: 2010 |
| 3. Conteúdo e estrutura | |
| É a matriz ou uma cópia? | é a matriz |
| Estágio do Conteúdo | concluido |
| Transferível | 1 |
| Tipo do Conteúdo | External Contribution |
| Tipo de Versão | publisher |
| Palavras-Chave | Label placement Lagrangean decomposition Lagrangean relaxation Maximum independent set |
| Resumo | The Maximum Independent Set (MIS) problem is a well-known problem where the aim is to find the maximum cardinality independent set in an associated graph. Map labeling problems can often be modeled as a MIS problem in a conflict graph, where labels are selected to be placed near graphical features not allowing overlaps (conflicts) between labels or between labels and features. However, the MIS problem is NP-hard and exact techniques present difficulties for solving some instances. Thus, this paper presents a Lagrangean decomposition to solve a map labeling problem, the Point-Feature Label Placement problem. We treated the problem by a conflict graph that is partitioned into small sub-problems and copies of some decision variables are done. These copies are used in the sub-problems constraints and in some constraints to ensure the equality between the original variables and their copies. After these steps, we relax these copy constraints in a Lagrangean way. Using instances proposed in the literature, our approach was able to prove the optimality for all of them, except one, and the results were better than the ones provided by a commercial solver. |
| Área | COMP |
| Arranjo | urlib.net > BDMCI > Fonds > Produção anterior à 2021 > LABAC > A lagrangean decomposition... |
| Conteúdo da Pasta doc | acessar |
| Conteúdo da Pasta source | não têm arquivos |
| Conteúdo da Pasta agreement | não têm arquivos |
| 4. Condições de acesso e uso | |
| Idioma | en |
| Arquivo Alvo | fulltextlorena.pdf |
| Grupo de Usuários | administrator marciana simone |
| Visibilidade | shown |
| Política de Arquivamento | denypublisher denyfinaldraft12 |
| Permissão de Leitura | deny from all and allow from 150.163 |
| Permissão de Atualização | não transferida |
| 5. Fontes relacionadas | |
| Repositório Espelho | sid.inpe.br/mtc-m19@80/2009/08.21.17.02.53 |
| Unidades Imediatamente Superiores | 8JMKD3MGPCW/3ESGTTP |
| Divulgação | WEBSCI; PORTALCAPES. |
| Acervo Hospedeiro | sid.inpe.br/mtc-m19@80/2009/08.21.17.02 |
| 6. Notas | |
| Campos Vazios | alternatejournal archivist callnumber copyholder copyright creatorhistory descriptionlevel e-mailaddress electronicmailaddress format isbn label lineage mark month nextedition notes number orcid pages parameterlist parentrepositories previousedition previouslowerunit progress project readergroup resumeid rightsholder schedulinginformation secondarydate secondarymark session shorttitle sponsor subject tertiarymark tertiarytype typeofwork url |
| 7. Controle da descrição | |
| e-Mail (login) | marciana |
| atualizar | |