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

DOI10.1016/J.DAM.2018.01.006MaRDI QIDQ1744248zbMATH OpenOpenAlexFDO

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

Publication date 20 April 2018

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

\(k\)-cliquebranch and boundclique search algorithmcombinatorial optimizationedge coloringgreedy coloringindependent setmaximum cliquenode coloring

Mathematics Subject Classification ID

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

Recommendations

• Edge coloring of graphs, uses, limitation, complexity
• Reducing graph coloring to clique search
• The complexity of an exotic edge coloring of graphs
• The clique-partitioning problem
• Estimating clique size by coloring the nodes of auxiliary graphs

Cites work

• A fast algorithm for the maximum clique problem
• An exact algorithm for the maximum clique problem
• Finding a Maximum Clique in an Arbitrary Graph
• Greedy algorithms for triangle free coloring
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• Monotonic matrices and clique search in graphs
• New methods to color the vertices of a graph
• Reducibility among combinatorial problems
• Speeding up Parallel Combinatorial Optimization Algorithms with Las Vegas Method
• Sur le coloriage des graphs
• Test case generators and computational results for the maximum clique problem

Cited in

(5)

• Edge coloring of graphs, uses, limitation, complexity
• Reducing graph coloring to clique search
• scientific article; zbMATH DE number 7407404 (Why is no real title available?)
• The complexity of an exotic edge coloring of graphs
• Splitting Edge Partitions of Graphs

Describes a project that uses

Uses Software

• OEIS

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1744248)