Combinatorial algorithms for the maximum \(k\)-plex problem

DOI10.1007/s10878-010-9338-2zbMath1245.90109OpenAlexW2078129907MaRDI QIDQ434188

Benjamin McClosky, Illya V. Hicks

Publication date: 10 July 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-010-9338-2

zbMATH Keywords

cliquecoloring\(k\)-plex

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)

Related Items (16)

Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ Two-phase heuristics for the \(k\)-club problem ⋮ Frequency-driven tabu search for the maximum \(s\)-plex problem ⋮ Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations ⋮ On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem ⋮ Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes ⋮ Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion ⋮ Discovering subjectively interesting multigraph patterns ⋮ Finding lasting dense subgraphs ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ Co-2-plex vertex partitions ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ A GPU based local search algorithm for the unweighted and weighted maximum \(s\)-plex problems ⋮ Continuous cubic formulations for cluster detection problems in networks ⋮ Optimization problems for the maximum \(k\)-plex

Uses Software

• Pajek
• Pajek datasets
• QUALEX
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Variable neighborhood search for the maximum clique
• An exact algorithm for the maximum clique problem
• Composition of stable set polyhedra
• An algorithm for finding a maximum clique in a graph
• A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
• A fast algorithm for the maximum clique problem
• Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring
• Solving the maximum clique problem using a tabu search approach
• Clique-detection models in computational biochemistry and genomics
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• The Co-2-plex Polytope and Integral Systems
• A graph‐theoretic generalization of the clique concept
• New methods to color the vertices of a graph
• On cliques in graphs

This page was built for publication: Combinatorial algorithms for the maximum \(k\)-plex problem