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

Files in This Item:
File Description SizeFormat 
Tese.pdf469.38 kBAdobe PDFView/Open


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.