Publication
Efficient domination through eigenvalues
| dc.contributor.author | Cardoso, Domingos M. | |
| dc.contributor.author | Lozin, Vadim V. | |
| dc.contributor.author | Luz, Carlos J. | |
| dc.contributor.author | Pacheco, Maria F. | |
| dc.date.accessioned | 2018-04-27T10:33:54Z | |
| dc.date.available | 2018-04-27T10:33:54Z | |
| dc.date.issued | 2016 | |
| dc.description.abstract | The paper begins with a new characterization of (k,τ)-regular sets. Then, using this result as well as the theory of star complements, we derive a simplex-like algorithm for determining whether or not a graph contains a (0,τ)-regular set. When τ = 1, this algorithm can be applied to solve the efficient dominating set problem which is known to be NP- complete. If −1 is not an eigenvalue of the adjacency matrix of the graph, this particular algorithm runs in polynomial time. However, although it doesn’t work in polynomial time in general, we report on its successful application to a vast set of randomly generated graphs. | pt_PT |
| dc.description.sponsorship | Research of the first, third and fourth authors partially supported by the Portuguese Foundation for Science and Technology (FCT-Fundação para a Ciência e a Tecnologia"), through the CIDMA - Center for Research and Development in Mathematics and Applications, within project UID/MAT/04106/2013 | pt_PT |
| dc.description.version | info:eu-repo/semantics/publishedVersion | pt_PT |
| dc.identifier.citation | Cardoso, Domingos M.; Lozin, Vadim V.; Luz, Carlos J.; Pacheco, Maria F. (2016). Efficient domination through eigenvalues. Discrete Applied Mathematics. ISSN 0166-218X. 214, p. 54-62 | pt_PT |
| dc.identifier.doi | 10.1016/j.dam.2016.06.014 | pt_PT |
| dc.identifier.issn | 0166-218X | |
| dc.identifier.uri | http://hdl.handle.net/10198/17357 | |
| dc.language.iso | eng | pt_PT |
| dc.peerreviewed | yes | pt_PT |
| dc.publisher | Elsevier | pt_PT |
| dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | pt_PT |
| dc.subject | (k,τ)-regular sets | pt_PT |
| dc.subject | graph eigenvalue | pt_PT |
| dc.subject | dominating induced matching | pt_PT |
| dc.subject | efficient dominating set | pt_PT |
| dc.title | Efficient domination through eigenvalues | pt_PT |
| dc.type | journal article | |
| dspace.entity.type | Publication | |
| oaire.awardURI | info:eu-repo/grantAgreement/FCT/5876/UID%2FMAT%2F04106%2F2013/PT | |
| oaire.citation.endPage | 62 | pt_PT |
| oaire.citation.startPage | 54 | pt_PT |
| oaire.citation.title | Discrete Applied Mathematics | pt_PT |
| oaire.citation.volume | 214 | pt_PT |
| oaire.fundingStream | 5876 | |
| 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 | |
| project.funder.identifier | http://doi.org/10.13039/501100001871 | |
| project.funder.name | Fundação para a Ciência e a Tecnologia | |
| rcaap.rights | openAccess | pt_PT |
| rcaap.type | article | pt_PT |
| relation.isAuthorOfPublication | e56596ca-3238-4fde-ace1-abb363a222e8 | |
| relation.isAuthorOfPublication.latestForDiscovery | e56596ca-3238-4fde-ace1-abb363a222e8 | |
| relation.isProjectOfPublication | 1eca6cd2-8e6f-490c-a592-a044cff040c5 | |
| relation.isProjectOfPublication.latestForDiscovery | 1eca6cd2-8e6f-490c-a592-a044cff040c5 |