Decomposing clique search problems into smaller instances based on node and edge colorings

DOI10.1016/j.dam.2018.01.006zbMath1384.05127OpenAlexW2790406481MaRDI QIDQ1744248

Sándor Szabó, Bogdán Zaválnij

Publication date: 20 April 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.01.006

zbMATH Keywords

combinatorial optimizationbranch and boundedge coloringindependent setmaximum cliquegreedy coloring\(k\)-cliquenode coloringclique search algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact algorithm for the maximum clique problem
• Test case generators and computational results for the maximum clique problem
• A fast algorithm for the maximum clique problem
• Greedy algorithms for triangle free coloring
• Speeding up Parallel Combinatorial Optimization Algorithms with Las Vegas Method
• Finding a Maximum Clique in an Arbitrary Graph
• New methods to color the vertices of a graph
• Reducibility among Combinatorial Problems
• Sur le coloriage des graphs

This page was built for publication: Decomposing clique search problems into smaller instances based on node and edge colorings