The Library
Efficient domination through eigenvalues
Tools
Tools
Tools
Cardoso, Domingos M., Lozin, Vadim V., Luz, Carlos J. and Pacheco, Maria F. (2016) Efficient domination through eigenvalues. Discrete Applied Mathematics, 214 . pp. 54-62. doi:10.1016/j.dam.2016.06.014 ISSN 0166-218X.
|
PDF
WRAP-efficient-domination-eigenvalues-Lozin-2016.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (804Kb) | Preview |
Official URL: https://doi.org/10.1016/j.dam.2016.06.014
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 NPcomplete. 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.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
| Library of Congress Subject Headings (LCSH): | Eigenvalues, Graph theory | ||||||||
| Journal or Publication Title: | Discrete Applied Mathematics | ||||||||
| Publisher: | Elsevier Science Ltd. | ||||||||
| ISSN: | 0166-218X | ||||||||
| Official Date: | 11 December 2016 | ||||||||
| Dates: |
|
||||||||
| Volume: | 214 | ||||||||
| Page Range: | pp. 54-62 | ||||||||
| DOI: | 10.1016/j.dam.2016.06.014 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 7 July 2016 | ||||||||
| Date of first compliant Open Access: | 19 July 2017 | ||||||||
| Funder: | Engineering and Physical Sciences Research Council (EPSRC), Portugal. Fundação para a Ciência e a tecnologia [Foundation for Science and Technology] (FCT) | ||||||||
| Grant number: | EP/L020408/1 (EPSRC), Project UID/MAT/04106/2013 (FCT) | ||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
