Spelling suggestions: "subject:"conjunto independente"" "subject:"onjunto independente""
1 |
Experimentos Computacionais com Implementações de Conjunto por Endereçamento Direto e o Problema de Conjunto Independente Máximo / Computational Experiments with Set Implementations by Direct Addressing and the Maximum Independent Set ProblemSantos, Marcio Costa January 2013 (has links)
SANTOS, M. C. Experimentos Computacionais com Implementações de Conjunto por Endereçamento Direto e o Problema de Conjunto Independente Máximo. 2013. 78 f. Dissertação (Mestrado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2013. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T19:19:39Z
No. of bitstreams: 1
2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-09-23T16:28:47Z (GMT) No. of bitstreams: 1
2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5) / Made available in DSpace on 2015-09-23T16:28:47Z (GMT). No. of bitstreams: 1
2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5)
Previous issue date: 2013 / The use of bit vectors is a usual practice for represent sets by direct addressing with the aim of reduce memory consumed and improve efficiency of applications with the use of bit parallel techniques. In this text, we study implementations for represent sets by direct addressed. The basic structure in this implementations is the bit vector. Besides that basic implementation, we implement two variations also. The first one is a stratification of the bit vector, while the second uses a hash table. The operations linked to the implemented structure are include and remove an element and the union and intersection of two sets. Especial attention is given to the use of bit parallel in this condition. The implementation of the different structures in this work use an base interface and a base abstract class, where the operations are defined and the bit parallel is used. An experimental comparative between this structures is carry out using enumerative algorithms for the maximum stable set problem. Two approaches are used in the implementation of the enumerative algorithms for the maximum stable set problem, both using the bit parallel in the representation of the graph and on the operations with subsets of vertices. The first one is a known branch-and-bound algorithm and the second uses the Russian dolls method. In both cases, the use of bit parallel improve efficiency when the lower bounds are calculated based in a clique cover of the vertices. The results of computational experiments are presented as comparison between the two algorithms and as an assessment of the structures implemented. These results show that the algorithm based on the method Russian Dolls is more efficient regarding runtime and the memory consumed. Furthermore, the experimental results also show that the use stratification and hash tables also allow more efficiency in the case of sparse graphs. / A utilização de vetores de bits é prática corrente na representação de conjuntos por endereçamento direto com o intuito de reduzir o espaço de memória necessário e melhorar o desempenho de aplicações com uso de técnicas de paralelismo em bits. Nesta dissertação, examinamos implementações para representação de conjuntos por endereçamento direto. A estrutura básica nessas implementações é o vetor de bits. No entanto, além dessa estrutura básica, implementamos também duas variações. A primeira delas consiste em uma estratificação de vetores de bits, enquanto a segunda emprega uma tabela de dispersão. As operações associadas às estruturas implementadas são a inclusão ou remoção de um elemento do conjunto e a união ou interseção de dois conjuntos. Especial atenção é dada ao uso de paralelismo em bits nessas operações. As implementações das diferentes estruturas nesta dissertação utilizam uma interface e uma implementação abstrata comuns, nas quais as operações são especificadas e o paralelismo em bits é explorado. A diferença entre as implementações está apenas na estrutura utilizada. Uma comparação experimental é realizada entre as diferentes estruturas utilizando algoritmos enumerativos para o problema de conjunto independente máximo. Duas abordagens são utilizadas na implementação de algoritmos enumerativos para o problema de conjunto independente máximo, ambas explorando o potencial de paralelismo em bits na representação do grafo e na operação sobre subconjuntos de vértices. A primeira delas é um algoritmo do tipo {em branch-and-boound} proposto na literatura e a segunda emprega o método das bonecas russas. Em ambos os casos, o uso de paralelismo em bits proporciona ganhos de eficiência quando empregado no cálculo de limites inferiores baseados em cobertura por cliques. Resultados de experimentos computacionais são apresentados como forma de comparação entre os dois algoritmos e como forma de avaliação das estruturas implementadas. Esses resultados permitem concluir que o algoritmo baseado no método das bonecas russas é mais eficiente quanto ao tempo de execução e quanto ao consumo de memória. Além disso, os resultados experimentais mostram também que o uso de estratificação e tabelas de dispersão permitem ainda maior eficiência no caso de grafos com muito vértices e poucas arestas.
|
2 |
Experimentos computacionais com implementações de conjunto por endereçamento direto e o problema de conjunto independente máximo / Computational experiments with set implementations by direct addressing and the maximum independent set problemSantos, Marcio Costa January 2013 (has links)
SANTOS, Marcio Costa. Experimentos computacionais com implementações de conjunto por endereçamento direto e o problema de conjunto independente máximo. 2013. 78 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T19:04:45Z
No. of bitstreams: 1
2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-20T11:59:49Z (GMT) No. of bitstreams: 1
2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5) / Made available in DSpace on 2016-07-20T11:59:49Z (GMT). No. of bitstreams: 1
2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5)
Previous issue date: 2013 / The use of bit vectors is a usual practice for represent sets by direct addressing with the aim of reduce memory consumed and improve efficiency of applications with the use of bit parallel techniques. In this text, we study implementations for represent sets by direct addressed. The basic structure in this implementations is the bit vector. Besides that basic implementation, we implement two variations also. The first one is a stratification of the bit vector, while the second uses a hash table. The operations linked to the implemented structure are include and remove an element and the union and intersection of two sets. Especial attention is given to the use of bit parallel in this condition. The implementation of the different structures in this work use an base interface and a base abstract class, where the operations are defined and the bit parallel is used. An experimental comparative between this structures is carry out using enumerative algorithms for the maximum stable set problem. Two approaches are used in the implementation of the enumerative algorithms for the maximum stable set problem, both using the bit parallel in the representation of the graph and on the operations with subsets of vertices. The first one is a known branch-and-bound algorithm and the second uses the Russian dolls method. In both cases, the use of bit parallel improve efficiency when the lower bounds are calculated based in a clique cover of the vertices. The results of computational experiments are presented as comparison between the two algorithms and as an assessment of the structures implemented. These results show that the algorithm based on the method Russian Dolls is more efficient regarding runtime and the memory consumed. Furthermore, the experimental results also show that the use stratification and hash tables also allow more efficiency in the case of sparse graphs. / A utilização de vetores de bits é prática corrente na representação de conjuntos por endereçamento direto com o intuito de reduzir o espaço de memória necessário e melhorar o desempenho de aplicações com uso de técnicas de paralelismo em bits. Nesta dissertação, examinamos implementações para representação de conjuntos por endereçamento direto. A estrutura básica nessas implementações é o vetor de bits. No entanto, além dessa estrutura básica, implementamos também duas variações. A primeira delas consiste em uma estratificação de vetores de bits, enquanto a segunda emprega uma tabela de dispersão. As operações associadas às estruturas implementadas são a inclusão ou remoção de um elemento do conjunto e a união ou interseção de dois conjuntos. Especial atenção é dada ao uso de paralelismo em bits nessas operações. As implementações das diferentes estruturas nesta dissertação utilizam uma interface e uma implementação abstrata comuns, nas quais as operações são especificadas e o paralelismo em bits é explorado. A diferença entre as implementações está apenas na estrutura utilizada. Uma comparação experimental é realizada entre as diferentes estruturas utilizando algoritmos enumerativos para o problema de conjunto independente máximo. Duas abordagens são utilizadas na implementação de algoritmos enumerativos para o problema de conjunto independente máximo, ambas explorando o potencial de paralelismo em bits na representação do grafo e na operação sobre subconjuntos de vértices. A primeira delas é um algoritmo do tipo {em branch-and-boound} proposto na literatura e a segunda emprega o método das bonecas russas. Em ambos os casos, o uso de paralelismo em bits proporciona ganhos de eficiência quando empregado no cálculo de limites inferiores baseados em cobertura por cliques. Resultados de experimentos computacionais são apresentados como forma de comparação entre os dois algoritmos e como forma de avaliação das estruturas implementadas. Esses resultados permitem concluir que o algoritmo baseado no método das bonecas russas é mais eficiente quanto ao tempo de execução e quanto ao consumo de memória. Além disso, os resultados experimentais mostram também que o uso de estratificação e tabelas de dispersão permitem ainda maior eficiência no caso de grafos com muito vértices e poucas arestas.
|
3 |
Geração de Facetas para Politopos de Conjuntos Independentes / Facet-generating Procedures for Stable Set PolytopesXavier, Alinson Santos January 2011 (has links)
XAVIER, Alinson Santos. Geração de Facetas para Politopos de Conjuntos Independentes. 2011. 141 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2011. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-23T19:04:42Z
No. of bitstreams: 1
2011_dis_asxavier.pdf: 1098827 bytes, checksum: b69a55ab904901d692a7afbf26cfbb04 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-23T19:10:07Z (GMT) No. of bitstreams: 1
2011_dis_asxavier.pdf: 1098827 bytes, checksum: b69a55ab904901d692a7afbf26cfbb04 (MD5) / Made available in DSpace on 2016-05-23T19:10:07Z (GMT). No. of bitstreams: 1
2011_dis_asxavier.pdf: 1098827 bytes, checksum: b69a55ab904901d692a7afbf26cfbb04 (MD5)
Previous issue date: 2011 / A stable set of a graph is a set of pairwise non-adjacent vertices. The maximum stable set problem is to find a stable set of maximum cardinality in a given graph. The maximum induced k-partite subgraph problem is to find k stable sets such that their union has maximum cardinality. Besides having applications in various fields, including computer vision, molecular biology and VLSI circuit design, these problems also model other important combinatorial problems, such as set packing and vertex coloring. In the present work, we study the facial structure of the polytopes associated with both problems. First, we describe a new facet generating procedure for the stable set polytope, which unifies and subsumes several previous procedures. Besides generating many well-known facet inducing inequalities, this procedure can also generate new facet-inducing inequalities which have not been previously described. Then, we study the maximum induced k-partite polytope formulated by asymmetric representatives. We describe its simplest facets, show that some of its facets arise from vertex induced subgraphs, and identify two classes of subgraphs which generate facets of the polytope. To reach these main results, we study the affine equivalence between polyhedra, and also develop a new facet generating procedure for general polyhedra which subsumes the many versions of the lifting of variables. / Um conjunto independente de um grafo é um subconjunto de vértices que não contém nenhum par de vértices vizinhos. O problema do maior conjunto independente consiste em encontrar um conjunto independente de cardinalidade máxima. O problema do maior subgrafo induzido k-partido consiste em encontrar k conjuntos independentes cuja união tenha cardinalidade máxima. Além de possuírem aplicação em diversas áreas, como visão computacional, biologia molecular e projeto de circuitos integrados, estes problemas também modelam outros problemas de otimização combinatória, como empacotamento de conjuntos e coloração de vértices. Neste trabalho, estudamos os politopos associados aos dois problemas. Primeiro, descrevemos um novo procedimento de geração de facetas para o politopo de conjuntos independentes, que unifica e generaliza diversos procedimentos anteriores. Além de gerar várias classes de desigualdades indutoras de facetas já conhecidas, este procedimento também gera novas desigualdades que ainda não foram descritas na literatura. Em seguida, estudamos o politopo do subgrafo induzido k-partido associado à formulação por representantes de cor. Identificamos suas facetas mais simples, mostramos que facetas podem ser geradas a partir de subgrafos induzidos, e descrevemos duas classes de subgrafos que geram facetas deste politopo. Para obter os principais resultados desta dissertação, fazemos um estudo da relação de afim-isomorfismo entre poliedros, e desenvolvemos um novo procedimento de conversão de faces em facetas que generaliza as diversas versões do procedimento de levantamento de variáveis.
|
4 |
GeraÃÃo de Facetas para Politopos de Conjuntos Independentes / Facet-generating Procedures for Stable Set PolytopesAlinson Santos Xavier 26 September 2011 (has links)
Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Um conjunto independente de um grafo à um subconjunto de vÃrtices que nÃo contÃm nenhum par de vÃrtices vizinhos. O problema do maior conjunto independente consiste em encontrar um conjunto independente de cardinalidade mÃxima. O problema do maior subgrafo induzido k-partido consiste em encontrar k conjuntos independentes cuja uniÃo tenha cardinalidade mÃxima. AlÃm de possuÃrem aplicaÃÃo em diversas Ãreas, como visÃo computacional, biologia molecular e projeto de circuitos integrados, estes problemas tambÃm modelam outros problemas de otimizaÃÃo combinatÃria, como empacotamento de conjuntos e coloraÃÃo de vÃrtices. Neste trabalho, estudamos os politopos associados aos dois problemas. Primeiro, descrevemos um novo procedimento de geraÃÃo de facetas para o politopo de conjuntos independentes, que unifica e generaliza diversos procedimentos anteriores. AlÃm de gerar vÃrias classes de desigualdades indutoras de facetas jà conhecidas, este procedimento tambÃm gera novas desigualdades que ainda nÃo foram descritas na literatura. Em seguida, estudamos o politopo do subgrafo induzido k-partido associado à formulaÃÃo por representantes de cor. Identificamos suas facetas mais simples, mostramos que facetas podem ser geradas a partir de subgrafos induzidos, e descrevemos duas classes de subgrafos que geram facetas deste politopo. Para obter os principais resultados desta dissertaÃÃo, fazemos um estudo da relaÃÃo de afim-isomorfismo entre poliedros, e desenvolvemos um novo procedimento de conversÃo de faces em facetas que generaliza as diversas versÃes do procedimento de levantamento de variÃveis. / A stable set of a graph is a set of pairwise non-adjacent vertices. The maximum stable set problem is to find a stable set of maximum cardinality in a given graph. The maximum induced k-partite subgraph problem is to find k stable sets such that their union has maximum cardinality. Besides having applications in various fields, including computer vision, molecular biology and VLSI circuit design, these problems also model other important combinatorial problems, such as set packing and vertex coloring. In the present work, we study the facial structure of the polytopes associated with both problems. First, we describe a new facet generating procedure for the stable set polytope, which unifies and subsumes several previous procedures. Besides generating many well-known facet inducing inequalities, this procedure can also generate new facet-inducing inequalities which have not been previously described. Then, we study the maximum induced k-partite polytope formulated by asymmetric representatives. We describe its simplest facets, show that some of its facets arise from vertex induced subgraphs, and identify two classes of subgraphs which generate facets of the polytope. To reach these main results, we study the affine equivalence between polyhedra, and also develop a new facet generating procedure for general polyhedra which subsumes the many versions of the lifting of variables.
|
5 |
Experimentos Computacionais com ImplementaÃÃes de Conjunto por EndereÃamento Direto e o Problema de Conjunto Independente MÃximo / Computational Experiments with Set Implementations by Direct Addressing and the Maximum Independent Set ProblemMarcio Costa Santos 13 September 2013 (has links)
CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / A utilizaÃÃo de vetores de bits à prÃtica corrente na representaÃÃo
de conjuntos por endereÃamento direto com o intuito de reduzir o espaÃo de memÃria necessÃrio e melhorar o desempenho de aplicaÃÃes com uso de tÃcnicas de paralelismo em bits.
Nesta dissertaÃÃo, examinamos implementaÃÃes para
representaÃÃo de conjuntos por endereÃamento direto.
A estrutura bÃsica nessas implementaÃÃes à o vetor de bits.
No entanto, alÃm dessa estrutura bÃsica, implementamos tambÃm duas
variaÃÃes. A primeira delas consiste em uma estratificaÃÃo de
vetores de bits, enquanto a segunda emprega uma tabela de
dispersÃo.
As operaÃÃes associadas Ãs estruturas implementadas sÃo a
inclusÃo ou remoÃÃo de um elemento do conjunto e a uniÃo ou
interseÃÃo de dois conjuntos. Especial atenÃÃo à dada ao uso
de paralelismo em bits nessas operaÃÃes. As implementaÃÃes das
diferentes estruturas nesta dissertaÃÃo utilizam uma interface e uma
implementaÃÃo abstrata comuns, nas quais as operaÃÃes sÃo
especificadas e o paralelismo em bits à explorado. A diferenÃa entre
as implementaÃÃes està apenas na estrutura utilizada. Uma comparaÃÃo
experimental à realizada entre as diferentes estruturas utilizando
algoritmos enumerativos para
o problema de conjunto independente mÃximo.
Duas abordagens sÃo utilizadas na implementaÃÃo de algoritmos
enumerativos para o problema de conjunto independente mÃximo,
ambas explorando o potencial de paralelismo em bits na
representaÃÃo do grafo e na operaÃÃo sobre subconjuntos de vÃrtices.
A primeira delas à um algoritmo do tipo {em branch-and-boound}
proposto na literatura e a segunda emprega o mÃtodo das bonecas russas. Em ambos os casos, o uso de paralelismo em bits proporciona ganhos de eficiÃncia quando empregado no cÃlculo de limites inferiores baseados em cobertura por cliques. Resultados de experimentos computacionais sÃo apresentados como forma de comparaÃÃo entre os dois algoritmos e como forma de avaliaÃÃo das estruturas implementadas. Esses resultados permitem concluir que o algoritmo baseado no mÃtodo das bonecas russas à mais eficiente quanto ao tempo de execuÃÃo e quanto ao consumo
de memÃria. AlÃm disso, os resultados experimentais mostram tambÃm que o uso de estratificaÃÃo e tabelas de dispersÃo permitem ainda maior eficiÃncia no caso de grafos com muito vÃrtices e poucas arestas. / The use of bit vectors is a usual practice for represent sets by
direct addressing with the aim of reduce memory consumed and improve
efficiency of applications with the use of bit parallel techniques.
In this text, we study implementations for represent sets by
direct addressed. The basic structure in this implementations is
the bit vector. Besides that basic implementation, we implement two
variations also. The first one is a stratification of the bit vector, while
the second uses a hash table.
The operations linked to the implemented structure are include and
remove an element and the union and intersection of two sets. Especial
attention is given to the use of bit parallel in this condition. The
implementation of the different structures in this work use an
base interface and a base abstract class, where the operations
are defined and the bit parallel is used. An experimental comparative
between this structures is carry out using enumerative algorithms for
the maximum stable set problem.
Two approaches are used in the implementation of the enumerative
algorithms for the maximum stable set problem, both using the bit parallel in the representation of the graph and on the operations
with subsets of vertices. The first one is a known branch-and-bound algorithm
and the second uses the Russian dolls method. In both cases, the use of
bit parallel improve efficiency when the lower bounds are calculated
based in a clique cover of the vertices. The results of computational experiments are presented as
comparison between the two algorithms and as an assessment of the structures
implemented. These results show that the algorithm based on the method
Russian Dolls is more efficient regarding runtime and the memory consumed.
Furthermore, the experimental results also show that the use
stratification and hash tables also allow
more efficiency in the case of sparse graphs.
|
Page generated in 0.079 seconds