A branch and bound algorithm for the maximum clique problem

Autor:	Gottfried Tinhofer, Luitpold Babel
Rok vydání:	1990
Předmět:	Discrete mathematics Block graph General Mathematics Management Science and Operations Research Clique graph Simplex graph Treewidth Combinatorics Clique problem Perfect graph Split graph Fractional coloring Software MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	ZOR Zeitschrift f�r Operations Research Methods and Models of Operations Research. 34:207-217
ISSN:	1432-5217 0340-9422
DOI:	10.1007/bf01415983
Popis:	We present a branch and bound algorithm for the maximum clique problem in arbitrary graphs. The main part of the algorithm consists in the determination of upper bounds by graph colorings. Using a modification of a known graph coloring method called DSATUR we simultaneously derive lower and upper bounds for the clique number.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::a95b901c5563a6d532d046d6b7e7ef7a https://doi.org/10.1007/bf01415983 Zobrazit plný text záznamu Full text from SpringerLink