Three-fast-searchable graphs
| gdc.relation.journal | Discrete Applied Mathematics | en_US |
| dc.contributor.author | Dereniowski, Dariusz | |
| dc.contributor.author | Diner, Öznur Yaşar | |
| dc.contributor.author | Dyer, Danny | |
| dc.contributor.other | Computer Engineering | |
| dc.contributor.other | 05. Faculty of Engineering and Natural Sciences | |
| dc.contributor.other | 01. Kadir Has University | |
| dc.date.accessioned | 2019-06-27T08:03:28Z | |
| dc.date.available | 2019-06-27T08:03:28Z | |
| dc.date.issued | 2013 | |
| 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.issn | 0166-218X | en_US |
| dc.identifier.issn | 0166-218X | |
| dc.identifier.scopus | 2-s2.0-84878273364 | 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.language.iso | en | en_US |
| dc.publisher | Elsevier Science Bv | en_US |
| dc.relation.ispartof | Discrete Applied Mathematics | |
| dc.rights | info:eu-repo/semantics/openAccess | en_US |
| 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 |
| dspace.entity.type | Publication | |
| gdc.author.institutional | Yaşar Diner, Öznur | |
| gdc.bip.impulseclass | C5 | |
| gdc.bip.influenceclass | C5 | |
| gdc.bip.popularityclass | C4 | |
| gdc.coar.access | open access | |
| gdc.coar.type | text::journal::journal article | |
| gdc.description.department | Fakülteler, Mühendislik ve Doğa Bilimleri Fakültesi, Bilgisayar Mühendisliği Bölümü | en_US |
| gdc.description.endpage | 1958 | |
| gdc.description.issue | 13-14 | |
| gdc.description.publicationcategory | Makale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı | en_US |
| gdc.description.scopusquality | Q2 | |
| gdc.description.startpage | 1950 | en_US |
| gdc.description.volume | 161 | en_US |
| gdc.description.wosquality | Q3 | |
| gdc.identifier.openalex | W2132813033 | |
| gdc.identifier.wos | WOS:000320680400015 | en_US |
| gdc.oaire.accesstype | HYBRID | |
| gdc.oaire.diamondjournal | false | |
| gdc.oaire.impulse | 1.0 | |
| gdc.oaire.influence | 3.4460408E-9 | |
| gdc.oaire.isgreen | true | |
| gdc.oaire.keywords | Computational complexity | |
| gdc.oaire.keywords | Fast searching | |
| gdc.oaire.keywords | Graph searching | |
| gdc.oaire.popularity | 4.7107926E-9 | |
| gdc.oaire.publicfunded | false | |
| gdc.oaire.sciencefields | 0211 other engineering and technologies | |
| gdc.oaire.sciencefields | 0102 computer and information sciences | |
| gdc.oaire.sciencefields | 02 engineering and technology | |
| gdc.oaire.sciencefields | 01 natural sciences | |
| gdc.openalex.fwci | 0.352 | |
| gdc.openalex.normalizedpercentile | 0.88 | |
| gdc.opencitations.count | 9 | |
| gdc.plumx.crossrefcites | 4 | |
| gdc.plumx.mendeley | 4 | |
| gdc.plumx.scopuscites | 9 | |
| gdc.scopus.citedcount | 9 | |
| gdc.wos.citedcount | 6 | |
| relation.isAuthorOfPublication | 84ac79d3-823a-4abf-9b15-e1383ec8a9f5 | |
| relation.isAuthorOfPublication.latestForDiscovery | 84ac79d3-823a-4abf-9b15-e1383ec8a9f5 | |
| relation.isOrgUnitOfPublication | fd8e65fe-c3b3-4435-9682-6cccb638779c | |
| relation.isOrgUnitOfPublication | 2457b9b3-3a3f-4c17-8674-7f874f030d96 | |
| relation.isOrgUnitOfPublication | b20623fc-1264-4244-9847-a4729ca7508c | |
| relation.isOrgUnitOfPublication.latestForDiscovery | fd8e65fe-c3b3-4435-9682-6cccb638779c |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Three-fast-searchable graphs.pdf
- Size:
- 446.37 KB
- Format:
- Adobe Portable Document Format
- Description: