Estimating clique size via discarding subgraphs
Abstract
given finite graph. In order to evaluate the proposed algorithm in practice we carry out
a large scale numerical experiment.
Full Text:
PDFReferences
E. Balas and J. Xue,
emph{Weighted and unweighted maximum clique algorithms with
upper bounds from fractional coloring,}
Algorithmica 15 (1996), pp.~397--412.
I. M. Bomze, M. Budinich, P. M. Pardalos and
M. Pelillo, emph{The Maximum Clique Problem, Handbook of
Combinatorial Optimization Vol. 4,} Kluwer Academic Publisher,
B. Borchers, emph{CSDP, A C Library for Semidefinite
Programming,} Optimization Methods and Software,
(1) (1999), pp.~613--623.
B. Borchers and J. G. Young. emph{Implementation of a primal-dual method
for SDP on a shared memory parallel architecture,} Computational
Optimization and Applications 37(3), (2007) pp.~355--369.
A. B'ota and M. Kr'esz. emph{A High Resolution Clique-based
Overlapping Community Detection Algorithm for Small-world Networks.}
Informatica, 39(2). (2015).
D. Brelaz,
emph{New methods to color the vertices of a graph,}
Communications of the ACM, 22 (1979), pp.~251--256.
J. C. Culberson, emph{Iterated Greedy Graph Coloring and the
Difficulty Landscape,} Technical Report, University of
Alberta, 1992.
C. Elphick and P. Wocjan,
emph{An inertial lower bound for the chromatic number of a graph,}
arXiv:1605.01978 (2016) url{https://arxiv.org/abs/1605.01978}
M. R. Garey and D. S. Johnson,
emph{Computers and Intractability: A Guide to the Theory of NP-completeness,}
Freeman, New York, 2003.
F. Harary, emph{Graph Theory,} Addison-Wesley, 1969.
J. Hasselberg, P. M. Pardalos, and G. Vairaktarakis,
emph{Test case generators and computational results for the maximum clique
problem,}
Journal of Global Optimization 3 (1993), pp.~463--482.
url{http://www.springerlink.com/content/p2m65n57u657605n}
D. Kumlander,
emph{Some Practical Algorithms to Solve the Maximal Clique Problem,}
PhD. Thesis, Tallin University of Technology, 2005.
S. Lamm, P. Sanders, C. Schulz, D. Strash, R.
F. Werneck. Finding Near-Optimial Independent Sets at
Scale. {it Proceedings of the 16th Meeting on Algorithm Engineering and
Experimentation (ALENEX'16).} 2016.
F. T. Leighton,
emph{A graph coloring algorithm for large scheduling problems,}
Journal of Research of National Bureau of Standards
(1979), pp.~489--506.
L. Lovasz, emph{On the Shannon Capacity of a Graph,}
IEEE Transactions on Information Theory, Volume 25 Issue 1,
January 1979 pp.~1--7.
P.R.J. "Ostergaa rd and A. P"oll"anen, emph{New Results on Tripod
Packings.} Discrete Comput Geom 61, 271--284 (2019).
C. H. Papadimitriou,
emph{Computational Complexity,}
Addison-Wesley Publishing Company, Inc., Reading, MA 1994.
N. J. A. Sloane,
emph{Challenge Problems: Independent Sets in Graphs,}
url{http://neilsloane.com/doc/graphs.html}
S. Stahl, emph{$n$-Tuple colorings and associated
graphs.} Journal of Combinatorial Theory, Series B Volume 20, Issue
, April 1976, pp.~185--203.
S. Szab'o
emph{Monotonic matrices and clique search in graphs,}
Annales Univ. Sci. Budapest., Sect. Comp.
(2013), pp.~307--322.
S. Szab'o and B. Zav'alnij, emph{Reducing graph
coloring to clique search,} Asia Pacific Journal of Mathematics, 1
(2016), pp.~64--85.
S. Szab'o and B. Zav'alnij, A different
approach to maximum clique search. emph{20th International Symposium on
Symbolic and Numeric Algorithms for Scientific Computing
(SYNASC2018)} pp.~310--316.
S. Szab'o and B. Zav'alnij, emph{Reducing
hypergraph coloring to clique search.} Discrete Applied Mathematics,
(2019), pp.~196--207.
Q. Wu and J-K. Hao, emph{A review on algorithms for maximum
clique problems,} European Journal of Operational Research.
Volume 242, Issue 3, 1 May 2015, pp.~693--709.
DOI: https://doi.org/10.31449/inf.v45i2.3107
This work is licensed under a Creative Commons Attribution 3.0 License.