A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques

DOI10.1287/IJOC.2020.0984MaRDI QIDQ5085477zbMATH OpenOpenAlexFDO

Authors Timo Gschwind, Stefan Irnich, Fabio Furini, Roberto Wolfler Calvo

Publication date 27 June 2022

Published in INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1723.pdf

zbMATH Keywords

social networksgraph decompositionclique relaxationsbranch-and-price algorithm

Mathematics Subject Classification ID

Combinatorics (05-XX) Operations research, mathematical programming (90-XX)

Recommendations

• Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement
• Cliques and clustering: A combinatorial approach
• Clique relaxations in social network analysis: the maximum k-plex problem
• On maximum ratio clique relaxations
• A branch-and-price procedure for clustering data that are graph connected

Cites work

• scientific article; zbMATH DE number 1424314 (Why is no real title available?)
• A fast algorithm for the maximum clique problem
• A graph coloring algorithm for large scale scheduling problems
• A survey on vertex coloring problems
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• Algorithms for the maximum k-club problem in graphs
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• An exact approach for the vertex coloring problem
• An introduction to timetabling
• Branch-and-price: Column generation for solving huge integer programs
• Branching in branch-and-price: A generic scheme
• Clique relaxations in social network analysis: the maximum k-plex problem
• Cliques and clustering: A combinatorial approach
• Column Generation
• Community structure in social and biological networks
• Efficiency of a Good But Not Linear Set Union Algorithm
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• Exact solution of graph coloring problems via constraint programming and column generation
• Identifying large robust network clusters via new compact formulations of maximum k-club problems
• Integer models and upper bounds for the 3-club problem
• Maximum weight relaxed cliques and Russian doll search revisited
• Maximum-weight stable sets and safe lower bounds for graph coloring
• Network Analysis
• On clique relaxation models in network analysis
• On inclusionwise maximal and maximum cardinality k-clubs in graphs
• On the maximum quasi-clique problem

Cited in

(1)

• Multivariate algorithmics for finding cohesive subnetworks

This page was built for publication: A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques

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