Please use this identifier to cite or link to this item:
https://hdl.handle.net/20.500.11851/5967
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kolla, A. | - |
dc.contributor.author | Koutis, I. | - |
dc.contributor.author | Madan, V. | - |
dc.contributor.author | Sinop, A. K. | - |
dc.date.accessioned | 2021-09-11T15:21:05Z | - |
dc.date.available | 2021-09-11T15:21:05Z | - |
dc.date.issued | 2018 | en_US |
dc.identifier.citation | 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, 9 July 2018 through 13 July 2018, , 137591 | en_US |
dc.identifier.isbn | 9783959770767 | - |
dc.identifier.issn | 1868-8969 | - |
dc.identifier.uri | https://doi.org/10.4230/LIPIcs.ICALP.2018.84 | - |
dc.identifier.uri | https://hdl.handle.net/20.500.11851/5967 | - |
dc.description.abstract | We initiate the study of spectral generalizations of the graph isomorphism problem. (a) The Spectral Graph Dominance (SGD) problem: On input of two graphs G and H does there exist a permutation ? such that G ?(H)? (b) The Spectrally Robust Graph Isomorphism (?-SRGI) problem: On input of two graphs G and H, find the smallest number ? over all permutations ? such that ?(H) G ?c?(H) for some c. SRGI is a natural formulation of the network alignment problem that has various applications, most notably in computational biology. G cH means that for all vectors x we have xTLGx ? cxTLHx, where LG is the Laplacian G. We prove NP-hardness for SGD. We also present a ?3-approximation algorithm for SRGI for the case when both G and H are bounded-degree trees. The algorithm runs in polynomial time when ? is a constant. © 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved. | en_US |
dc.description.sponsorship | National Science Foundation: 1319376, CCF-1319376, CCF-1452923 Cold and Arid Regions Environmental and Engineering Research Institute, Chinese Academy of Sciences | en_US |
dc.description.sponsorship | Avast;RSJ | en_US |
dc.language.iso | en | en_US |
dc.publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing | en_US |
dc.relation.ispartof | Leibniz International Proceedings in Informatics, LIPIcs | en_US |
dc.rights | info:eu-repo/semantics/closedAccess | en_US |
dc.subject | Graph isomorphism | en_US |
dc.subject | Graph similarity | en_US |
dc.subject | Network alignment | en_US |
dc.title | Spectrally Robust Graph Isomorphism | en_US |
dc.type | Conference Object | en_US |
dc.department | Faculties, Faculty of Engineering, Department of Computer Engineering | en_US |
dc.department | Fakülteler, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü | tr_TR |
dc.identifier.volume | 107 | en_US |
dc.identifier.scopus | 2-s2.0-85049782838 | en_US |
dc.institutionauthor | Sinop, Ali Kemal | - |
dc.identifier.doi | 10.4230/LIPIcs.ICALP.2018.84 | - |
dc.relation.publicationcategory | Konferans Öğesi - Uluslararası - Kurum Öğretim Elemanı | en_US |
dc.relation.conference | 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 | en_US |
dc.identifier.scopusquality | - | - |
item.openairetype | Conference Object | - |
item.languageiso639-1 | en | - |
item.grantfulltext | none | - |
item.fulltext | No Fulltext | - |
item.openairecristype | http://purl.org/coar/resource_type/c_18cf | - |
item.cerifentitytype | Publications | - |
crisitem.author.dept | 02.3. Department of Computer Engineering | - |
Appears in Collections: | Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection |
CORE Recommender
SCOPUSTM
Citations
1
checked on Dec 21, 2024
Page view(s)
66
checked on Dec 23, 2024
Google ScholarTM
Check
Altmetric
Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.