首页    期刊浏览 2024年11月27日 星期三
登录注册

文章基本信息

  • 标题:Spectrally Robust Graph Isomorphism
  • 作者:Alexandra Kolla ; Ioannis Koutis ; Vivek Madan
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:107
  • 页码:84:1-84:13
  • DOI:10.4230/LIPIcs.ICALP.2018.84
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We initiate the study of spectral generalizations of the graph isomorphism problem. b) The Spectral Graph Dominance (SGD) problem: On input of two graphs G and H does there exist a permutation pi such that G preceq pi(H)? c) The Spectrally Robust Graph Isomorphism (kappa-SRGI) problem: On input of two graphs G and H, find the smallest number kappa over all permutations pi such that pi(H) preceq G preceq kappa c pi(H) for some c. SRGI is a natural formulation of the network alignment problem that has various applications, most notably in computational biology. G preceq c H means that for all vectors x we have x^T L_G x <= c x^T L_H x, where L_G is the Laplacian G. We prove NP-hardness for SGD. We also present a kappa^3-approximation algorithm for SRGI for the case when both G and H are bounded-degree trees. The algorithm runs in polynomial time when kappa is a constant.
  • 关键词:Network Alignment; Graph Isomorphism; Graph Similarity
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有