@article{einstein,
    author = "Albert Einstein",
    title = "{Zur Elektrodynamik bewegter K{\"o}rper}. ({German})
    [{On} the electrodynamics of moving bodies]",
    journal = "Annalen der Physik",
    volume = "322",
    number = "10",
    pages = "891--921",
    year = "1905",
    DOI = "http://dx.doi.org/10.1002/andp.19053221004",
    keywords = "physics"
}

@book{dirac,
    title = {The Principles of Quantum Mechanics},
    author = {Paul Adrien Maurice Dirac},
    isbn = {9780198520115},
    series = {International series of monographs on physics},
    year = {1981},
    publisher = {Clarendon Press},
    keywords = {physics}
}

@online{knuthwebsite,
    author = "Donald Knuth",
    title = "Knuth: Computers and Typesetting",
    url  = "http://www-cs-faculty.stanford.edu/~uno/abcde.html",
    addendum = "(accessed: 01.09.2016)",
    keywords = "latex,knuth"
}

@inbook{knuth-fa,
    author = "Donald E. Knuth",
    title = "Fundamental Algorithms",
    publisher = "Addison-Wesley",
    year = "1973",
    chapter = "1.2",
    keywords  = "knuth,programming"
}

@article{bk1973,
	author = "Coen Bron and Joep Kerbosch",
	title = "Algorithm 457: Finding All Cliques of an Undirected Graph",
	journal = "Communication of the ACM",
	volume = "16",
	number = "9",
	pages = "575--577",
	year = "1973",
	DOI = "https://doi.org/10.1145%2F362342.362367"
}

@inproceedings{DBLP:conf/dmtcs/TomitaS03,
  author       = {Etsuji Tomita and
                  Tomokazu Seki},
  editor       = {Cristian Calude and
                  Michael J. Dinneen and
                  Vincent Vajnovszki},
  title        = {An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique},
  booktitle    = {Discrete Mathematics and Theoretical Computer Science, 4th International
                  Conference, {DMTCS} 2003, Dijon, France, July 7-12, 2003. Proceedings},
  series       = {Lecture Notes in Computer Science},
  volume       = {2731},
  pages        = {278--289},
  publisher    = {Springer},
  year         = {2003},
  url          = {https://doi.org/10.1007/3-540-45066-1\_22},
  doi          = {10.1007/3-540-45066-1\_22},
  timestamp    = {Tue, 14 May 2019 10:00:50 +0200},
  biburl       = {https://dblp.org/rec/conf/dmtcs/TomitaS03.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{LI20171,
title = {On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem},
journal = {Computers \& Operations Research},
volume = {84},
pages = {1-15},
year = {2017},
issn = {0305-0548},
doi = {https://doi.org/10.1016/j.cor.2017.02.017},
url = {https://www.sciencedirect.com/science/article/pii/S0305054817300576},
author = {Chu-Min Li and Hua Jiang and Felip Manyà},
keywords = {Maximum clique problem, Branch-and-bound, Branching ordering, Incremental MaxSAT Reasoning},
abstract = {When searching for a maximum clique in a graph G, branch-and-bound algorithms in the literature usually focus on the minimization of the number of branches generated at each search tree node. We call dynamic strategy this minimization without any constraint, because it induces a dynamic vertex ordering in G during the search. In this paper, we introduce a static strategy that minimizes the number of branches subject to the constraint that a static vertex ordering in G must be kept during the search. We analyze the two strategies and show that they are complementary. From this complementarity, we propose a new algorithm, called MoMC, that combines the strengths of the two strategies into a single algorithm. The reported experimental results show that MoMC is generally better than the algorithms implementing a single strategy.}
}

@inproceedings{10.3233/978-1-61499-672-9-939,
author = {Jiang, Hua and Li, Chu-Min and Many\`{a}, Felip},
title = {Combining Efficient Preprocessing and Incremental MaxSAT Reasoning for MaxClique in Large Graphs},
year = {2016},
isbn = {9781614996712},
publisher = {IOS Press},
address = {NLD},
url = {https://doi.org/10.3233/978-1-61499-672-9-939},
doi = {10.3233/978-1-61499-672-9-939},
abstract = {We describe a new exact algorithm for MaxClique, called LMC (short for Large MaxClique), that is especially suited for large sparse graphs. LMC is competitive because it combines an efficient preprocessing procedure and incremental MaxSAT reasoning in a branch-and-bound scheme. The empirical results show that LMC outperforms existing exact MaxClique algorithms on large sparse graphs from real-world applications.},
booktitle = {Proceedings of the Twenty-Second European Conference on Artificial Intelligence},
pages = {939–947},
numpages = {9},
location = {The Hague, The Netherlands},
series = {ECAI'16}
}

@article{SanSegundo2016,
author = "Pablo, San Segundo and Alvaro, Lopez and Jorge Artieda and Panos M. Pardalos",
title = "A parallel maximum clique algorithm for large and massive sparse graphs",
year="2017",
journal = "Optimization Letters",
pages = "343--358",
volume = "11",
DOI = "https://doi.org/10.1007/s11590-016-1019-3"

}

@Article{a6040618,
AUTHOR = {McCreesh, Ciaran and Prosser, Patrick},
TITLE = {Multi-Threading a State-of-the-Art Maximum Clique Algorithm},
JOURNAL = {Algorithms},
VOLUME = {6},
YEAR = {2013},
NUMBER = {4},
PAGES = {618--635},
URL = {https://www.mdpi.com/1999-4893/6/4/618},
ISSN = {1999-4893},
ABSTRACT = {We present a threaded parallel adaptation of a state-of-the-art maximum clique algorithm for dense, computationally challenging graphs. We show that near-linear speedups are achievable in practice and that superlinear speedups are common. We include results for several previously unsolved benchmark problems.},
DOI = {10.3390/a6040618}
}

@article{fujii1982efficient,
  title={On efficient algorithms for finding a maximum clique},
  author={Fujii, T},
  journal={Tech. Rep. IECE},
  volume={81},
  pages={25--34},
  year={1982}
}

@InProceedings{10.1007/978-3-642-11440-3_18,
author="Tomita, Etsuji
and Sutani, Yoichi
and Higashi, Takanori
and Takahashi, Shinya
and Wakatsuki, Mitsuo",
editor="Rahman, Md. Saidur
and Fujita, Satoshi",
title="A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique",
booktitle="WALCOM: Algorithms and Computation",
year="2010",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="191--203",
abstract="This paper proposes new approximate coloring and other related techniques which markedly improve the run time of the branch-and-bound algorithm MCR (J. Global Optim., 37, 95--111, 2007), previously shown to be the fastest maximum-clique-finding algorithm for a large number of graphs. The algorithm obtained by introducing these new techniques in MCR is named MCS. It is shown that MCS is successful in reducing the search space quite efficiently with low overhead. Consequently, it is shown by extensive computational experiments that MCS is remarkably faster than MCR and other existing algorithms. It is faster than the other algorithms by an order of magnitude for several graphs. In particular, it is faster than MCR for difficult graphs of very high density and for very large and sparse graphs, even though MCS is not designed for any particular type of graphs. MCS can be faster than MCR by a factor of more than 100,000 for some extremely dense random graphs.",
isbn="978-3-642-11440-3"
}

@misc{almasri2023parallelizing,
      title={Parallelizing Maximal Clique Enumeration on GPUs}, 
      author={Mohammad Almasri and Yen-Hsiang Chang and Izzat El Hajj and Rakesh Nagi and Jinjun Xiong and Wen-mei Hwu},
      year={2023},
      eprint={2212.01473},
      archivePrefix={arXiv},
      primaryClass={cs.DC}
}

@article{SANSEGUNDO2011571,
title = {An exact bit-parallel algorithm for the maximum clique problem},
journal = {Computers \& Operations Research},
volume = {38},
number = {2},
pages = {571-581},
year = {2011},
issn = {0305-0548},
doi = {https://doi.org/10.1016/j.cor.2010.07.019},
url = {https://www.sciencedirect.com/science/article/pii/S0305054810001504},
author = {Pablo {San Segundo} and Diego Rodríguez-Losada and Agustín Jiménez},
keywords = {Maximum clique, Bit string, Branch and bound, Coloring, Bit-parallelism},
abstract = {This paper presents a new exact maximum clique algorithm which improves the bounds obtained in state of the art approximate coloring by reordering the vertices at each step. Moreover, the algorithm can make full use of bit strings to sort vertices in constant time as well as to compute graph transitions and bounds efficiently, exploiting the ability of CPUs to process bitwise operations in blocks of size the ALU register word. As a result it significantly outperforms a current leading algorithm.}
}

@article{Janez2007,
author = {Konc, Janez and Janežić, Dušanka},
year = {2007},
month = {01},
pages = {},
title = {An improved branch and bound algorithm for the maximum clique problem},
volume = {58},
journal = {MATCH - Communications in Mathematical and in Computer Chemistry}
}

@article{
Chang2020,
	author = {Chang, Lijun},
	title = {Efficient maximum clique computation and enumeration over large sparse graphs},
	year = {2020},
	publisher = {Spinger},
	url = {https://doi.org/10.1007/s00778-020-00602-z},
	doi = {10.1007/s00778-020-00602-z},
	abstract = {This paper studies the problem of maximum clique computation (MCC) over sparse graphs, as large real-world graphs are usually sparse. In the literature, the problem of MCC over sparse graphs has been studied separately and less extensively than its dense counterpart—MCC over dense graphs—and advanced algorithmic techniques that are developed for MCC over dense graphs have not been utilized in the existing MCC solvers for sparse graphs. In this paper, we design an algorithm $$\mathsf {MC\text {-}BRB}$$for sparse graphs which transforms an instance of MCC over a large sparse graph G to instances of k-clique finding (KCF) over dense subgraphs of G, each of which can be computed by the existing MCC solvers for dense graphs. To further improve the efficiency, we then develop a new branch-reduce-&-bound framework for KCF over dense graphs by proposing light-weight reducing techniques and leveraging the advanced branching and bounding techniques that are used in the existing MCC solvers for dense graphs. In addition, we also design an ego-centric algorithm $$\mathsf {MC\text {-}EGO}$$for heuristically computing a near-maximum clique in near-linear time, and we extend our $$\mathsf {MC\text {-}BRB}$$algorithm to enumerate all maximum cliques. Finally, we parallelize our algorithms to exploit multiple CPU cores. We conduct extensive empirical studies on large real graphs and demonstrate the efficiency and effectiveness of our techniques.
},
	journal = {The VLDB Journal},
	pages = {999-1022}
}

@inproceedings{nr,
  title = {The Network Data Repository with Interactive Graph Analytics and Visualization},
  author={Ryan A. Rossi and Nesreen K. Ahmed},
  booktitle = {AAAI},
  url={https://networkrepository.com},
  year={2015}
}

@article{Li_Quan_2010, title={An Efficient Branch-and-Bound Algorithm Based on MaxSAT for the Maximum Clique Problem}, volume={24}, url={https://ojs.aaai.org/index.php/AAAI/article/view/7536}, DOI={10.1609/aaai.v24i1.7536}, abstractNote={ &lt;p&gt; State-of-the-art branch-and-bound algorithms for the maximum clique problem (Maxclique) frequently use an upper bound based on a partition P of a graph into independent sets for a maximum clique of the graph, which cannot be very tight for imperfect graphs. In this paper we propose a new encoding from Maxclique into MaxSAT and use MaxSAT technology to improve the upper bound based on the partition P. In this way, the strength of specific algorithms for Maxclique in partitioning a graph and the strength of MaxSAT technology in propositional reasoning are naturally combined to solve Maxclique. Experimental results show that the approach is very effective on hard random graphs and on DIMACS Maxclique benchmarks, and allows to close an open DIMACS problem. &lt;/p&gt; }, number={1}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Li, Chu-Min and Quan, Zhe}, year={2010}, month={Jul.}, pages={128-133} }

@article{SanSegundoBBMCR,
author = {San Segundo, Pablo and Matia, Fernando and Rodríguez-Losada, Diego and Hernando, Miguel},
year = {2011},
month = {03},
pages = {467-479},
title = {An improved bit parallel exact maximum clique algorithm},
volume = {7},
journal = {Optimization Letters},
doi = {10.1007/s11590-011-0431-y}
}

@article{pattillo2013clique,
  title={On clique relaxation models in network analysis},
  author={Pattillo, Jeffrey and Youssef, Nataly and Butenko, Sergiy},
  journal={European Journal of Operational Research},
  volume={226},
  number={1},
  pages={9--18},
  year={2013},
  publisher={Elsevier}
}

@article{etzion1998coding,
  title={Greedy and heuristic algorithms for codes and colorings},
  author={Etzion, Tuvi and Ostergard, Patric RJ},
  journal={IEEE Transactions on Information Theory},
  volume={44},
  number={1},
  pages={382--388},
  year={1998},
  publisher={IEEE}
}

@article{boginski2006market,
  title={Mining market data: A network approach},
  author={Boginski, Vladimir and Butenko, Sergiy and Pardalos, Panos M},
  journal={Computers \& Operations Research},
  volume={33},
  number={11},
  pages={3171--3184},
  year={2006},
  publisher={Elsevier}
}

@InProceedings{Tomita2010MCS,
author="Tomita, Etsuji
and Sutani, Yoichi
and Higashi, Takanori
and Takahashi, Shinya
and Wakatsuki, Mitsuo",
editor="Rahman, Md. Saidur
and Fujita, Satoshi",
title="A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique",
booktitle="WALCOM: Algorithms and Computation",
year="2010",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="191--203",
abstract="This paper proposes new approximate coloring and other related techniques which markedly improve the run time of the branch-and-bound algorithm MCR (J. Global Optim., 37, 95--111, 2007), previously shown to be the fastest maximum-clique-finding algorithm for a large number of graphs. The algorithm obtained by introducing these new techniques in MCR is named MCS. It is shown that MCS is successful in reducing the search space quite efficiently with low overhead. Consequently, it is shown by extensive computational experiments that MCS is remarkably faster than MCR and other existing algorithms. It is faster than the other algorithms by an order of magnitude for several graphs. In particular, it is faster than MCR for difficult graphs of very high density and for very large and sparse graphs, even though MCS is not designed for any particular type of graphs. MCS can be faster than MCR by a factor of more than 100,000 for some extremely dense random graphs.",
isbn="978-3-642-11440-3"
}

@online{nvidia,
  author = {NVIDIA},
  title = {{CUDA Programming Guide}},
  url={https://docs.nvidia.com/cuda/cuda-c-programming-guide/}
}

@InProceedings{McCreeshMCSClique,
author="McCreesh, Ciaran
and Ndiaye, Samba Ndojh
and Prosser, Patrick
and Solnon, Christine",
editor="Rueher, Michel",
title="Clique and Constraint Models for Maximum Common (Connected) Subgraph Problems",
booktitle="Principles and Practice of Constraint Programming",
year="2016",
publisher="Springer International Publishing",
address="Cham",
pages="350--368",
abstract="The maximum common subgraph problem is to find the largest subgraph common to two given graphs. This problem can be solved either by constraint-based search, or by reduction to the maximum clique problem. We evaluate these two models using modern algorithms, and see that the best choice depends mainly upon whether the graphs have labelled edges. We also study a variant of this problem where the subgraph is required to be connected. We introduce a filtering algorithm for this property and show that it may be combined with a restricted branching technique for the constraint-based approach. We show how to implement a similar branching technique in clique-inspired algorithms. Finally, we experimentally compare approaches for the connected version, and see again that the best choice depends on whether graphs have labels.",
isbn="978-3-319-44953-1"
}

@misc{maloddognin2009maximumcliquesproteinstructure,
      title={Maximum Cliques in Protein Structure Comparison}, 
      author={Noël Malod-Dognin and Rumen Andonov and Nicola Yanev},
      year={2009},
      eprint={0910.0977},
      archivePrefix={arXiv},
      primaryClass={q-bio.BM},
      url={https://arxiv.org/abs/0910.0977}, 
}


