Please use this identifier to cite or link to this item:
|Title:||Spectrally robust graph isomorphism||Authors:||Kolla, A.
Sinop, A. K.
|Issue Date:||2018||Publisher:||Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing||Source:||45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, 9 July 2018 through 13 July 2018, , 137591||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.||URI:||https://doi.org/10.4230/LIPIcs.ICALP.2018.84
|Appears in Collections:||Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering|
Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
Show full item record
checked on Sep 23, 2022
checked on Dec 26, 2022
Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.