Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/12863
Title: | Majorantes para a ordem de subgrafos induzidos k-regulares |
Author: | Pinheiro, Sofia Alexandra Marques Jorge |
Advisor: | Cardoso, Domingos Moreira |
Keywords: | Matemática Teoria espectral (Matemática) Teoria de grafos Matrizes (Matemática) |
Defense Date: | 2014 |
Publisher: | Universidade de Aveiro |
Abstract: | Muitos dos problemas de otimização em grafos reduzem-se à determinação
de um subconjunto de vértices de cardinalidade máxima que induza
um subgrafo k-regular. Uma vez que a determinação da ordem
de um subgrafo induzido k-regular de maior ordem é, em geral, um
problema NP-difícil, são deduzidos novos majorantes, a determinar em
tempo polinomial, que em muitos casos constituam boas aproximações
das respetivas soluções ótimas. Introduzem-se majorantes espetrais
usando uma abordagem baseada em técnicas de programação convexa
e estabelecem-se condições necessárias e suficientes para que sejam
atingidos. Adicionalmente, introduzem-se majorantes baseados no espetro
das matrizes de adjacência, laplaciana e laplaciana sem sinal. É
ainda apresentado um algoritmo não polinomial para a determinação de
umsubconjunto de vértices de umgrafo que induz umsubgrafo k-regular
de ordem máxima para uma classe particular de grafos. Finalmente,
faz-se um estudo computacional comparativo com vários majorantes e
apresentam-se algumas conclusões. Many optimization problems on graphs are reduced to the determination of a subset of vertices of maximum cardinality inducing a k-regular subgraph. Since the determination of the order of a k-regular induced subgraph of highest order is in general a NP-hard problem, new upper bounds, determined in polynomial time which in many cases are good approximations of the respective optimal solutions are deduced. Using convex programming techniques, spectral upper boundswere introduced jointly with necessary and sufficient conditions for those upper bounds be achieved. Additionally, upper bounds based on adjacency, Laplacian and signless Laplacian spectrum are introduced. Furthermore, a nonpolynomial time algorithm for determining a subset of vertices of a graph which induces a maximum k-regular induced subgraph for a particular class is presented. Finally, a comparative computational study is provided jointly with a few conclusions. |
Description: | Doutoramento em Matemática |
URI: | http://hdl.handle.net/10773/12863 |
Appears in Collections: | UA - Teses de doutoramento DMat - Teses de doutoramento |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.