Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/16157
Full metadata record
DC FieldValueLanguage
dc.contributor.authorCardoso, Domingos M.pt
dc.contributor.authorLozin, V. V.pt
dc.contributor.authorLuz, C. J.pt
dc.contributor.authorPacheco, M. F.pt
dc.date.accessioned2016-09-22T16:51:59Z-
dc.date.issued2016-12-11-
dc.identifier.issn0166-218Xpt
dc.identifier.urihttp://hdl.handle.net/10773/16157-
dc.description.abstractThe 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.pt
dc.language.isoengpt
dc.publisherElsevierpt
dc.relationFCT - UID/MAT/04106/2013pt
dc.relationEPSRC - grant EP/L020408/1pt
dc.rightsrestrictedAccesspor
dc.subjectEfficient dominating setpt
dc.subjectDominating induced matchingpt
dc.subject(k,τ)(k,τ)-regular setspt
dc.subjectGraph eigenvaluept
dc.titleEfficient domination through eigenvaluespt
dc.typearticlept
dc.peerreviewedyespt
ua.distributioninternationalpt
degois.publication.firstPage54pt
degois.publication.lastPage62pt
degois.publication.titleDiscrete Applied Mathematicspt
degois.publication.volume214pt
dc.date.embargo10000-01-01-
dc.identifier.doi10.1016/j.dam.2016.06.014pt
Appears in Collections:CIDMA - Artigos
OGTCG - Artigos

Files in This Item:
File Description SizeFormat 
1-s2.0-S0166218X16302931-main.pdfElectronic version427.59 kBAdobe PDFrestrictedAccess


FacebookTwitterLinkedIn
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.