Three-fast-searchable graphs

dc.contributor.author Yaşar Diner, Öznur
dc.contributor.author Diner, Öznur Yaşar
dc.contributor.author Dyer, Danny
dc.contributor.other Computer Engineering
dc.date.accessioned 2019-06-27T08:03:28Z
dc.date.available 2019-06-27T08:03:28Z
dc.date.issued 2013
dc.department Fakülteler, Mühendislik ve Doğa Bilimleri Fakültesi, Bilgisayar Mühendisliği Bölümü en_US
dc.description.abstract In 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.citationcount 5
dc.identifier.doi 10.1016/j.dam.2013.03.004 en_US
dc.identifier.endpage 1958
dc.identifier.issn 0166-218X en_US
dc.identifier.issn 0166-218X
dc.identifier.issue 13-14
dc.identifier.scopus 2-s2.0-84878273364 en_US
dc.identifier.scopusquality Q2
dc.identifier.startpage 1950 en_US
dc.identifier.uri https://hdl.handle.net/20.500.12469/795
dc.identifier.uri https://doi.org/10.1016/j.dam.2013.03.004
dc.identifier.volume 161 en_US
dc.identifier.wos WOS:000320680400015 en_US
dc.identifier.wosquality Q3
dc.institutionauthor Diner, Öznur Yaşar en_US
dc.language.iso en en_US
dc.publisher Elsevier Science Bv en_US
dc.relation.journal Discrete Applied Mathematics en_US
dc.relation.publicationcategory Makale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı en_US
dc.rights info:eu-repo/semantics/openAccess en_US
dc.scopus.citedbyCount 9
dc.subject Computational complexity en_US
dc.subject Fast searching en_US
dc.subject Graph searching en_US
dc.title Three-fast-searchable graphs en_US
dc.type Article en_US
dc.wos.citedbyCount 5
dspace.entity.type Publication
relation.isAuthorOfPublication 84ac79d3-823a-4abf-9b15-e1383ec8a9f5
relation.isAuthorOfPublication.latestForDiscovery 84ac79d3-823a-4abf-9b15-e1383ec8a9f5
relation.isOrgUnitOfPublication fd8e65fe-c3b3-4435-9682-6cccb638779c
relation.isOrgUnitOfPublication.latestForDiscovery fd8e65fe-c3b3-4435-9682-6cccb638779c

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: