Please use this identifier to cite or link to this item:
Title: Spectrally robust graph isomorphism
Authors: Kolla, A.
Koutis, I.
Madan, V.
Sinop, A. K.
Keywords: Graph isomorphism
Graph similarity
Network alignment
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.
ISBN: 9783959770767
ISSN: 1868-8969
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

CORE Recommender


checked on Sep 23, 2022

Page view(s)

checked on Dec 26, 2022

Google ScholarTM



Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.