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
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
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 Sep 23, 2022

Page view(s)

6
checked on Dec 26, 2022

Google ScholarTM

Check

Altmetric


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