A New Spectral Bound on the Clique Number of Graphs

被引：0
作者：
Bulo, Samuel Rota [1 ]
Pelillo, Marcello [1 ]
机构：
[1] Univ Venice, Dipartimento Informat, I-30123 Venice, Italy
来源：
STRUCTURAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION | 2010年 / 6218卷
关键词：
MAXIMAL CLIQUES; ISOMORPHISM; RECOGNITION; ORDER;
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
Many computer vision and patter recognition problems are intimately related to the maximum clique problem. Due to the intractability of this problem, besides the development of heuristics, a research direction consists in trying to find good bounds on the clique number of graphs. This paper introduces a new spectral upper bound on the clique number of graphs, which is obtained by exploiting an invariance of a continuous characterization of the clique number of graphs introduced by Motzkin and Straus. Experimental results on random graphs show the superiority of our bounds over the standard literature.
引用
收藏
页码：680 / 689
页数：10
相关论文
共 50 条
  • [31] Sublinear-Space and Bounded-Delay Algorithms for Maximal Clique Enumeration in Graphs
    Conte, Alessio
    Grossi, Roberto
    Marino, Andrea
    Versari, Luca
    ALGORITHMICA, 2020, 82 (06) : 1547 - 1573
  • [32] Sublinear-Space and Bounded-Delay Algorithms for Maximal Clique Enumeration in Graphs
    Alessio Conte
    Roberto Grossi
    Andrea Marino
    Luca Versari
    Algorithmica, 2020, 82 : 1547 - 1573
  • [33] Graphs with forbidden subgraphs and leaf number
    Mafuta P.
    Mazorodze J.P.
    Mushanyu J.
    Nhawu G.
    Afrika Matematika, 2018, 29 (7-8) : 1073 - 1080
  • [34] Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
    Coudert, David
    Ducoffe, Guillaume
    Popa, Alexandru
    SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2018, : 2765 - 2784
  • [35] Index-based top kα-maximal-clique enumeration over uncertain graphs
    Jing Bai
    Junfeng Zhou
    Ming Du
    Ziyang Chen
    The Journal of Supercomputing, 2022, 78 : 19372 - 19400
  • [36] TREEWIDTH VERSUS CLIQUE NUMBER. I. GRAPH CLASSES WITH A FORBIDDEN STRUCTURE
    Dallard, Clement
    Milanic, Martin
    Storgel, Kenny
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (04) : 2618 - 2646
  • [37] ON THE NUMBER OF CYCLES OF GRAPHS AND VC-DIMENSION
    Mofidi, Alireza
    FACTA UNIVERSITATIS-SERIES MATHEMATICS AND INFORMATICS, 2022, 37 (01): : 121 - 135
  • [38] An improved lower bound on the independence number of a graph
    Henning, Michael A.
    Loewenstein, Christian
    DISCRETE APPLIED MATHEMATICS, 2014, 179 : 120 - 128
  • [39] On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
    Alcon, Liliana
    Bonomo, Flavia
    Duran, Guillermo
    Gutierrez, Marisa
    Mazzoleni, Maria Pia
    Ries, Bernard
    Valencia-Pabon, Mario
    DISCRETE APPLIED MATHEMATICS, 2018, 234 : 12 - 21
  • [40] The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs
    Arvind, Vikraman
    Fuhlbrueck, Frank
    Koebler, Johannes
    Kuhnert, Sebastian
    Rattan, Gaurav
    ACM TRANSACTIONS ON COMPUTATION THEORY, 2022, 14 (02)
12345