Three-fast-searchable graphs

dc.contributor.authorDereniowski, Dariusz
dc.contributor.authorDiner, Öznur Yaşar
dc.contributor.authorDyer, Danny
dc.date.accessioned2019-06-27T08:03:28Z
dc.date.available2019-06-27T08:03:28Z
dc.date.issued2013
dc.departmentFakülteler, Mühendislik ve Doğa Bilimleri Fakültesi, Bilgisayar Mühendisliği Bölümüen_US
dc.description.abstractIn the edge searching problem searchers move from vertex to vertex in a graph to capture an invisible fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which at every move a new edge of the graph G must be guaranteed to be free of the intruder. That is once all searchers are placed the graph G is cleared in exactly vertical bar E(G)vertical bar moves. Such a restriction obviously necessitates a larger number of searchers. We examine this model and characterize graphs for which 2 or 3 searchers are sufficient. We prove that the corresponding decision problem is NP-complete. (C) 2013 Elsevier B.V. All rights reserved.en_US]
dc.identifier.citation5
dc.identifier.doi10.1016/j.dam.2013.03.004en_US
dc.identifier.endpage1958
dc.identifier.issn0166-218Xen_US
dc.identifier.issn0166-218X
dc.identifier.issue13-14
dc.identifier.scopus2-s2.0-84878273364en_US
dc.identifier.scopusqualityQ2
dc.identifier.startpage1950en_US
dc.identifier.urihttps://hdl.handle.net/20.500.12469/795
dc.identifier.urihttps://doi.org/10.1016/j.dam.2013.03.004
dc.identifier.volume161en_US
dc.identifier.wosWOS:000320680400015en_US
dc.identifier.wosqualityQ3
dc.institutionauthorDiner, Öznur Yaşaren_US
dc.language.isoenen_US
dc.publisherElsevier Science Bven_US
dc.relation.journalDiscrete Applied Mathematicsen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectComputational complexityen_US
dc.subjectFast searchingen_US
dc.subjectGraph searchingen_US
dc.titleThree-fast-searchable graphsen_US
dc.typeArticleen_US
dspace.entity.typePublication

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Three-fast-searchable graphs.pdf
Size:
446.37 KB
Format:
Adobe Portable Document Format
Description: