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

DOI10.1287/IJOC.2020.0984OpenAlexW2801405741MaRDI QIDQ5085477FDOQ5085477

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)

Cites Work

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

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)