Encontrados 6 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...
O método simplex generalizado
Cardoso, Domingos MoreiraApresenta-se um novo método para a resolução de problemas de Programação Linear, que se designa por método simplex generalizado, por se considerar que generaliza o método simplex clássico. Com efeito, as sucessivas soluções admissíveis, que se vão determinando ao longo da sua aplicação, podem pertencer ao interior relativo de faces de dimensão superior a zero, fazendo-se os respectivos deslocamentos, entre esta...
| Financiadores do RCAAP | |||||||
|
|
|
|
|
|
||