Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/16157
Title: | Efficient domination through eigenvalues |
Author: | Cardoso, Domingos M. Lozin, V. V. Luz, C. J. Pacheco, M. F. |
Keywords: | Efficient dominating set Dominating induced matching (k,τ)(k,τ)-regular sets Graph eigenvalue |
Issue Date: | 11-Dec-2016 |
Publisher: | Elsevier |
Abstract: | The paper begins with a new characterization of (k,τ)(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,τ)(0,τ)-regular set. When τ=1τ=1, this algorithm can be applied to solve the efficient dominating set problem which is known to be NP-complete. If −1−1 is not an eigenvalue of the adjacency matrix of the graph, this particular algorithm runs in polynomial time. However, although it does not work in polynomial time in general, we report on its successful application to a vast set of randomly generated graphs. |
Peer review: | yes |
URI: | http://hdl.handle.net/10773/16157 |
DOI: | 10.1016/j.dam.2016.06.014 |
ISSN: | 0166-218X |
Appears in Collections: | CIDMA - Artigos OGTCG - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
1-s2.0-S0166218X16302931-main.pdf | Electronic version | 427.59 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.