Spelling suggestions: "subject:"conectividade"" "subject:"desconectividade""
1 |
Estudo de casos de complexidade de colorações gulosa de vértices e de arestas / Case studies of complexity of greedy colorings of vertices and edgesOliveira, Ana Karolinna Maia de January 2011 (has links)
OLIVEIRA, Ana Karolinna Maia de. Estudo de casos de complexidade de colorações gulosa de vértices e de arestas. 2011. 58 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2011. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T18:03:48Z
No. of bitstreams: 1
2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T12:34:49Z (GMT) No. of bitstreams: 1
2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) / Made available in DSpace on 2016-07-13T12:34:49Z (GMT). No. of bitstreams: 1
2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5)
Previous issue date: 2011 / The vertices and edges colorings problems, which consists in determine the smallest number of colors needed to color the vertices and edges of a graph, respectively, so that adjacent vertices and adjacent edges, respectively, have distinct colors, are computationally hard problems and recurring subject of research in graph theory due to numerous practical problems they model. In this work, we study the worst performance of greedy algorithms for coloring vertices and edges. The greedy algorithm has the following general principle: to receive, one by one, the vertices (respect. edges) of the graph to be colored by assigning always the smallest possible color to the vertex (resp. edge) to be colored. We note that so greedy coloring the edges of a graph is equivalent to greedily coloring its line graph, this being the greatest interest in research on greedy edges coloring. The worst performance of the Algorithms is measured by the greatest number of colors they can use. In the case of greedy vertex coloring, this is the number of Grundy or greedy chromatic number of the graph. For the edge coloring, this is the greedy chromatic index or Grundy index of the graph. It is known that determining the Grundy number of any graph is NP-hard. The complexity of determining the Grundy index of any graph was however an open problem. In this dissertation, we prove two complexity results. We prove that the Grundy number of a (q,q−4)-graph can be determined in polynomial time. This class contains strictly the class of cografos P4-sparse for which the same result had been established. This result generalizes so those results. The presented algorithm uses the primeval decomposition of graphs, determining the parameter in linear time. About greedy edge coloring, we prove that the problem of determining the Grundy index is NP-complete for general graphs and polynomial for catepillar graphs, implying that the Grundy number is polynomial for graphs of line of caterpillars. More specifically, we prove that the Grundy index of a caterpillar is D or D+1 and present a polynomial algorithm to determine it exactly. / Os problemas de coloracão de vértices e de arestas, que consistem em determinar o menor número de cores necessárias para colorir os vértices e arestas de um grafo, respectivamente, de forma que vértices adjacentes e arestas adjacentes, respectivamente, possuem cores distintas, são problemas computacionalmente difíceis e são objeto de pesquisa recorrente em teoria do grafos em virtude de inúmeros problemas práticos que eles modelam. No presente trabalho, estudamos o pior desempenho dos algoritmos gulosos de coloração de vértices e de arestas. O algoritmo guloso tem o seguinte princípio geral: receber, um a um, os vértices (respect. as arestas) do grafo a ser colorido, atribuindo sempre a menor cor possível ao vértice (resp. aresta) a ser colorido. Observamos que colorir de forma gulosa as arestas de um grafo equivale a colorir de forma gulosa o seu grafo linha, tendo sido este o maior interesse na pesquisa em coloração gulosa de arestas. O pior desempenho dos algoritmos é medido pelo maior número de cores que eles podem utilizar. No caso da coloração gulosa de vértices, esse é o número de Grundy ou número cromático guloso do grafo. No caso da coloração de arestas, esse é o íındice cromático guloso ou íındice de Grundy do grafo. Sabe-se que determinar o número de Grundy de um grafo qualquer é NP-difícil. A complexidade de determinar o índice de Grundy de um grafo qualquer era entretanto um problema em aberto. Na presente dissertação, provamos dois resultados de complexidade. Provamos que o número de Grundy de um grafo (q,q−4) pode ser determinado em tempo polinomial. Essa classe contém estritamente a classe dos cografos e P4-esparsos para os quais o mesmo resultado havia sido estabelecido. Esse resultado generaliza portanto aqueles resultados. O algoritmo apresentado usa a decomposição primeval desses grafos, determinando o parâmetro em tempo linear. No que se refere à coloração de arestas, provamos que o problema de determinar o índice de Grundy é NP-completo para grafos em geral e polinomial para grafos caterpillar, implicando que o número de Grundy é polinomial para os grafos linha desses. Mais especificamente provamos que o índice de Grundy dos caterpillar é D ou D+1 e apresentamos um algoritmo polinomial para determiná-lo exatamente.
|
2 |
Estudo de casos de complexidade de coloraÃÃes gulosa de vÃrtices e de arestas / Case studies of complexity of greedy colorings of vertices and edgesAna Karolinna Maia de Oliveira 07 April 2011 (has links)
Os problemas de colorac Ëao de vÂertices e de arestas, que consistem em determinar o menor
nÂumero de cores necessÂarias para colorir os vÂertices e arestas de um grafo, respectivamente, de
forma que vÂertices adjacentes e arestas adjacentes, respectivamente, possuem cores distintas,
sËao problemas computacionalmente difÂıceis e sËao objeto de pesquisa recorrente em teoria do
grafos em virtude de inÂumeros problemas prÂaticos que eles modelam.
No presente trabalho, estudamos o pior desempenho dos algoritmos gulosos de colorac Ëao
de vÂertices e de arestas. O algoritmo guloso tem o seguinte princÂıpio geral: receber, um a um,
os vÂertices (respect. as arestas) do grafo a ser colorido, atribuindo sempre a menor cor possÂıvel
ao vÂertice (resp. aresta) a ser colorido. Observamos que colorir de forma gulosa as arestas de
um grafo equivale a colorir de forma gulosa o seu grafo linha, tendo sido este o maior interesse
na pesquisa em colorac Ëao gulosa de arestas.
O pior desempenho dos algoritmos Âe medido pelo maior nÂumero de cores que eles podem
utilizar. No caso da colorac Ëao gulosa de vÂertices, esse Âe o nÂumero de Grundy ou nÂumero
cromÂatico guloso do grafo. No caso da colorac Ëao de arestas, esse Âe o Âındice cromÂatico guloso
ou Âındice de Grundy do grafo. Sabe-se que determinar o nÂumero de Grundy de um grafo qualquer
Âe NP-difÂıcil. A complexidade de determinar o Âındice de Grundy de um grafo qualquer era
entretanto um problema em aberto.
Na presente dissertac Ëao, provamos dois resultados de complexidade. Provamos que o
nÂumero de Grundy de um grafo (q,q−4) pode ser determinado em tempo polinomial. Essa
classe contÂem estritamente a classe dos cografos e P4-esparsos para os quais o mesmo resultado
havia sido estabelecido. Esse resultado generaliza portanto aqueles resultados. O algoritmo
apresentado usa a decomposicÂËao primeval desses grafos, determinando o parËametro em tempo
linear.
No que se refere `a colorac Ëao de arestas, provamos que o problema de determinar o Âındice
de Grundy Âe NP-completo para grafos em geral e polinomial para grafos caterpillar, implicando
que o nÂumero de Grundy Âe polinomial para os grafos linha desses. Mais especificamente
provamos que o Âındice de Grundy dos caterpillar Âe D ou D+1 e apresentamos um algoritmo
polinomial para determinÂa-lo exatamente. / The vertices and edges colorings problems, which consists in determine the smallest number
of colors needed to color the vertices and edges of a graph, respectively, so that adjacent
vertices and adjacent edges, respectively, have distinct colors, are computationally hard problems
and recurring subject of research in graph theory due to numerous practical problems
they model.
In this work, we study the worst performance of greedy algorithms for coloring vertices and
edges. The greedy algorithm has the following general principle: to receive, one by one, the
vertices (respect. edges) of the graph to be colored by assigning always the smallest possible
color to the vertex (resp. edge) to be colored. We note that so greedy coloring the edges of a
graph is equivalent to greedily coloring its line graph, this being the greatest interest in research
on greedy edges coloring.
The worst performance of the Algorithms is measured by the greatest number of colors they
can use. In the case of greedy vertex coloring, this is the number of Grundy or greedy chromatic
number of the graph. For the edge coloring, this is the greedy chromatic index or Grundy index
of the graph. It is known that determining the Grundy number of any graph is NP-hard. The
complexity of determining the Grundy index of any graph was however an open problem.
In this dissertation, we prove two complexity results. We prove that the Grundy number of
a (q,q−4)-graph can be determined in polynomial time. This class contains strictly the class
of cografos P4-sparse for which the same result had been established. This result generalizes so
those results. The presented algorithm uses the primeval decomposition of graphs, determining
the parameter in linear time.
About greedy edge coloring, we prove that the problem of determining the Grundy index is
NP-complete for general graphs and polynomial for catepillar graphs, implying that the Grundy
number is polynomial for graphs of line of caterpillars. More specifically, we prove that the
Grundy index of a caterpillar is D or D+1 and present a polynomial algorithm to determine it
exactly.
|
3 |
Estudo de casos de complexidade de colorações gulosa de vértices e de arestas / Case studies of complexity of greedy colorings of vertices and edgesOliveira, Ana Karolinna Maia de January 2011 (has links)
OLIVEIRA, Ana Karolinna Maia de. Estudo de casos de complexidade de colorações gulosa de vértices e de arestas. 2011. 58 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-24T19:36:17Z
No. of bitstreams: 1
2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T19:36:55Z (GMT) No. of bitstreams: 1
2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) / Made available in DSpace on 2016-05-24T19:36:55Z (GMT). No. of bitstreams: 1
2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5)
Previous issue date: 2011 / The vertices and edges colorings problems, which consists in determine the smallest number of colors needed to color the vertices and edges of a graph, respectively, so that adjacent vertices and adjacent edges, respectively, have distinct colors, are computationally hard problems and recurring subject of research in graph theory due to numerous practical problems they model. In this work, we study the worst performance of greedy algorithms for coloring vertices and edges. The greedy algorithm has the following general principle: to receive, one by one, the vertices (respect. edges) of the graph to be colored by assigning always the smallest possible color to the vertex (resp. edge) to be colored. We note that so greedy coloring the edges of a graph is equivalent to greedily coloring its line graph, this being the greatest interest in research on greedy edges coloring. The worst performance of the Algorithms is measured by the greatest number of colors they can use. In the case of greedy vertex coloring, this is the number of Grundy or greedy chromatic number of the graph. For the edge coloring, this is the greedy chromatic index or Grundy index of the graph. It is known that determining the Grundy number of any graph is NP-hard. The complexity of determining the Grundy index of any graph was however an open problem. In this dissertation, we prove two complexity results. We prove that the Grundy number of a (q,q−4)-graph can be determined in polynomial time. This class contains strictly the class of cografos P4-sparse for which the same result had been established. This result generalizes so those results. The presented algorithm uses the primeval decomposition of graphs, determining the parameter in linear time. About greedy edge coloring, we prove that the problem of determining the Grundy index is NP-complete for general graphs and polynomial for catepillar graphs, implying that the Grundy number is polynomial for graphs of line of caterpillars. More specifically, we prove that the Grundy index of a caterpillar is D or D+1 and present a polynomial algorithm to determine it exactly. / Os problemas de colorac¸ ˜ao de v´ertices e de arestas, que consistem em determinar o menor n´umero de cores necess´arias para colorir os v´ertices e arestas de um grafo, respectivamente, de forma que v´ertices adjacentes e arestas adjacentes, respectivamente, possuem cores distintas, s˜ao problemas computacionalmente dif´ıceis e s˜ao objeto de pesquisa recorrente em teoria do grafos em virtude de in´umeros problemas pr´aticos que eles modelam. No presente trabalho, estudamos o pior desempenho dos algoritmos gulosos de colorac¸ ˜ao de v´ertices e de arestas. O algoritmo guloso tem o seguinte princ´ıpio geral: receber, um a um, os v´ertices (respect. as arestas) do grafo a ser colorido, atribuindo sempre a menor cor poss´ıvel ao v´ertice (resp. aresta) a ser colorido. Observamos que colorir de forma gulosa as arestas de um grafo equivale a colorir de forma gulosa o seu grafo linha, tendo sido este o maior interesse na pesquisa em colorac¸ ˜ao gulosa de arestas. O pior desempenho dos algoritmos ´e medido pelo maior n´umero de cores que eles podem utilizar. No caso da colorac¸ ˜ao gulosa de v´ertices, esse ´e o n´umero de Grundy ou n´umero crom´atico guloso do grafo. No caso da colorac¸ ˜ao de arestas, esse ´e o ´ındice crom´atico guloso ou ´ındice de Grundy do grafo. Sabe-se que determinar o n´umero de Grundy de um grafo qualquer ´e NP-dif´ıcil. A complexidade de determinar o ´ındice de Grundy de um grafo qualquer era entretanto um problema em aberto. Na presente dissertac¸ ˜ao, provamos dois resultados de complexidade. Provamos que o n´umero de Grundy de um grafo (q,q−4) pode ser determinado em tempo polinomial. Essa classe cont´em estritamente a classe dos cografos e P4-esparsos para os quais o mesmo resultado havia sido estabelecido. Esse resultado generaliza portanto aqueles resultados. O algoritmo apresentado usa a decomposic¸˜ao primeval desses grafos, determinando o parˆametro em tempo linear. No que se refere `a colorac¸ ˜ao de arestas, provamos que o problema de determinar o ´ındice de Grundy ´e NP-completo para grafos em geral e polinomial para grafos caterpillar, implicando que o n´umero de Grundy ´e polinomial para os grafos linha desses. Mais especificamente provamos que o ´ındice de Grundy dos caterpillar ´e D ou D+1 e apresentamos um algoritmo polinomial para determin´a-lo exatamente.
|
Page generated in 0.042 seconds