Encontrados 8 documentos, a visualizar página 1 de 1
Determinação de conjuntos (0,2)-regulares em grafos e aplicações
Pacheco, Maria F.; Cardoso, Domingos Moreira; Luz, Carlos J.Um conjunto (kappa,tau)-regular num grafo é um subconjunto de vértices que induz um subgrafo kappa-regular com a seguinte propriedade: cada vértice não pertencente ao conjunto tem nele exactamente tau vizinhos. Neste trabalho apresenta-se um novo algoritmo para a determinação de conjuntos (0,2)-regulares em grafos linha com a aplicação na determinação de emparelhamentos máximos em grafos com recurso à programaç...
Determination of (0,2)-regular sets in graphs and applications
Pacheco, Maria F.; Cardoso, Domingos Moreira; Luz, Carlos J.A (k,τ)-regular set in a graph is a subset of vertices inducing a k-regular subgraph and such that each vertex not in the set has exactly τ neighbours in it. We will present a new algorithm for the determination of (0,2)-regular sets as well as its application to the determination of maximum matchings in arbitrary graphs.
Convex quadratic programming applied to the stability number of a graph
Pacheco, Maria F.; Cardoso, Domingos Moreira; Luz, Carlos J.We deal with graphs whose stability number can be determined by a convex quadratic program and describe algorithmic techniques for the determination of maximum stable sets in such graphs.
Maximum matching by convex quadratic programming based o an adverse graph conje...
Pacheco, Maria F.; Cardoso, Domingos Moreira; Luz, Carlos J.In this talk, we describe a procedure for determining a maximum stable set in a graph with convex-$QP$ stability number (which is a graph whose stability number can be determined by solving a convex quadratic programming problem) unless there is a subgraph for which neither the optimal value of the convex quadratic program nor the least adjacency eigenvalue changes when the neighborhood of any vertex is dele...
Convex quadratic programming applied to the stability number of a graph
Pacheco, Maria F.; Cardoso, Domingos Moreira; Luz, Carlos J.We deal with graphs whose stability number can be determined by a convex quadratic program and describe algorithmic techniques for the determination of maximum stabe sets in such graphs (except there is an induced subgraph with least adjacency eigenvalue and optimal value of the convex quadratic program not changing if the neighbourhood of any vertex is deleted). Such a graph is called adverse. Assuming that ev...
Algorithmic strategies for the recognition of graphs with convex
Pacheco, Maria F.; Luz, Carlos J.; Cardoso, Domingos M.A major difficulty in the recognition of graphs with convex quadratic stability number is the existence of adverse subgraphs (an adverse subgraph is a subgraph such that the smallest eigenvalue of its adjacency matrix doesn’t change when any vertex or the neighbourhood of any vertex is deleted). It is a challenge to find adverse graphs without convex quadratic stability number. We present the main results ...
Algorithmic strategies for the recognition of graphs with convex quadratic stab...
Pacheco, Maria F.; Luz, Carlos J.; Cardoso, Domingos M.A major difficulty in the recognition of graphs with convex quadratic stability number is the existence of adverse subgraphs (an adverse subgraph is a subgraph such that the smallest eigenvalue of its adjacency matrix doesn’t change when any vertex or the neighbourhood of any vertex is deleted). It is a challenge to find adverse graphs without convex quadratic stability number. We present the main results ...
A heuristic for the stability number of a graph based on convex quadratic progr...
Cavique, Luís; Luz, Carlos J.Recently, a characterization of the Lov´asz theta number based on convex quadratic programming was established. As a consequence of this formulation, we introduce a new upper bound on the stability number of a graph that slightly improves the theta number. Like this number, the new bound can be characterized as the minimum of a function whose values are the optimum values of convex quadratic programs. This pape...
| Financiadores do RCAAP | |||||||
|
|
|
|
|
|
||