Estimating clique size via discarding subgraphs
Abstract
The paper will present a method to establish an upper bound on the clique number of agiven finite graph. In order to evaluate the proposed algorithm in practice we carry outa large scale numerical experiment.References
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.3107Downloads
Published
How to Cite
Issue
Section
License
Authors retain copyright in their work. By submitting to and publishing with Informatica, authors grant the publisher (Slovene Society Informatika) the non-exclusive right to publish, reproduce, and distribute the article and to identify itself as the original publisher.
All articles are published under the Creative Commons Attribution license CC BY 3.0. Under this license, others may share and adapt the work for any purpose, provided appropriate credit is given and changes (if any) are indicated.
Authors may deposit and share the submitted version, accepted manuscript, and published version, provided the original publication in Informatica is properly cited.
