Publication
Maximum matching by convex quadratic programming based o an adverse graph conjecture
| dc.contributor.author | Pacheco, Maria F. | |
| dc.contributor.author | Cardoso, Domingos M. | |
| dc.contributor.author | Luz, Carlos J. | |
| dc.date.accessioned | 2014-10-02T14:23:21Z | |
| dc.date.available | 2014-10-02T14:23:21Z | |
| dc.date.issued | 2012 | |
| dc.description.abstract | 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 deleted. Such a graph is called adverse. Assuming the trueness of the adverse graph conjecture (which states that every adverse graph has convex-$QP$ stability number), an algorithm for the recognition of graphs with convex-$QP$ stability number is introduced and applied to the determination of a maximum matching. With this procedure, we decide if a graph has or not convex-$QP$ stability number or a counterexample for the conjecture is determined. So far, from our computations, no counterexample was found and we believe that this conjecture is true. | por |
| dc.identifier.citation | Pacheco, Maria F.; Cardoso, Domingos Moreira; Luz, Carlos J. (2012). Maximum matching by convex quadratic programming based o an adverse graph conjecture. In ECCO XXV - 25th Conference of Eurepean Chapter of Operational Research. Antalya, Turkey | por |
| dc.identifier.uri | http://hdl.handle.net/10198/10686 | |
| dc.language.iso | por | por |
| dc.peerreviewed | yes | por |
| dc.subject | Maximum matching | por |
| dc.subject | Convex quadratic programming | por |
| dc.title | Maximum matching by convex quadratic programming based o an adverse graph conjecture | por |
| dc.type | conference object | |
| dspace.entity.type | Publication | |
| oaire.citation.conferencePlace | Antalya, Turkey | por |
| oaire.citation.title | ECCO XXV - 25th Conference of Eurepean Chapter of Operational Research | por |
| person.familyName | Pacheco | |
| person.givenName | Maria F. | |
| person.identifier.ciencia-id | F319-DAC3-8F15 | |
| person.identifier.orcid | 0000-0001-7915-0391 | |
| person.identifier.scopus-author-id | 36802474600 | |
| rcaap.rights | openAccess | por |
| rcaap.type | conferenceObject | por |
| relation.isAuthorOfPublication | e56596ca-3238-4fde-ace1-abb363a222e8 | |
| relation.isAuthorOfPublication.latestForDiscovery | e56596ca-3238-4fde-ace1-abb363a222e8 |