Encontrados 15 documentos, a visualizar página 1 de 2
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...
EUREKit - Jogos Matemáticos
Fernandes, Florbela P.; Pacheco, Maria F.; Pereira, Ana I.A exposição EUREKit do Instituto Politécnico de Bragança é constituída por seis módulos de jogos de estratégia e de tabuleiro. A partir da exploração dos jogos e da sua relação com a Matemática, este projecto pretende, de uma forma didáctica e atractiva, contribuir para aumentar o interesse dos alunos de todos os níveis de ensino pela disciplina, motivar para a aprendizagem, melhorar a autoconfiança, a concentr...
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 ...
Experiências com a exposição EUREKit
Pacheco, Maria F.; Fernandes, Florbela P.; Pereira, Ana I.; Fernandes, Paula O.A exposição itinerante de jogos matemáticos EureKit, do Instituto Politécnico de Bragança, é constituída por seis módulos de jogos de estratégia e de tabuleiro. A partir da exploração dos jogos e da sua relação com a Matemática, este projecto pretende, de uma forma didáctica e atractiva, contribuir para aumentar o interesse dos alunos pela disciplina de Matemática. Neste trabalho, apresenta-se a experiência efe...
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 ...
Recognition of graphs with convex quadratic stability number
Pacheco, Maria F.; Cardoso, Domingos M.A stable set of a graph is a set of mutually non-adjacent vertices. The determination of a maximum size stable set, which is called maximum stable set, and the determination of its size, which is called stability number, are central combinatorial optimization problems. However, given a nonnegative integer k, to determine if a graph G has a stable set of size k is NP-complete. In this paper we deal with graphs f...
| Financiadores do RCAAP | |||||||
|
|
|
|
|
|
||