Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.11851/5967
Title: Spectrally robust graph isomorphism
Authors: Kolla, A.
Koutis, I.
Madan, V.
Sinop, A. K.
Keywords: Graph isomorphism
Graph similarity
Network alignment
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
https://hdl.handle.net/20.500.11851/5967
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

SCOPUSTM   
Citations

1
checked on Mar 23, 2024

Page view(s)

16
checked on Mar 25, 2024

Google ScholarTM

Check




Altmetric


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