Clique-detection models in computational biochemistry and genomics

DOI10.1016/j.ejor.2005.05.026zbMath1125.92025OpenAlexW2035372875MaRDI QIDQ2491763

Wilbert E. Wilhelm, Sergiy I. Butenko

Publication date: 29 May 2006

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2005.05.026

zbMATH Keywords

optimizationclique-detection

Mathematics Subject Classification ID

Applications of graph theory (05C90) Applications of mathematical programming (90C90) Biochemistry, molecular biology (92C40) Genetics and epigenetics (92D10)

Related Items (52)

Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs ⋮ Minimum cost edge blocker clique problem ⋮ Multi-attribute community detection in international trade network ⋮ Finding maximum subgraphs with relatively large vertex connectivity ⋮ Isolation concepts for efficiently enumerating dense subgraphs ⋮ Exact algorithms for the minimum cost vertex blocker clique problem ⋮ All roads lead to Rome -- new search methods for the optimal triangulation problem ⋮ Detecting robust cliques in graphs subject to uncertain edge failures ⋮ Two-phase heuristics for the \(k\)-club problem ⋮ Infra-chromatic bound for exact maximum clique search ⋮ Optimizing experimental design in genetics ⋮ Extended and discretized formulations for the maximum clique problem ⋮ Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations ⋮ Integer models and upper bounds for the 3‐club problem ⋮ Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming ⋮ An opposition-based memetic algorithm for the maximum quasi-clique problem ⋮ On atomic cliques in temporal graphs ⋮ An exact algorithm for the maximum probabilistic clique problem ⋮ On maximum ratio clique relaxations ⋮ Minimum k‐cores and the k‐core polytope ⋮ Co-2-plex polynomials ⋮ A new branch-and-bound algorithm for the maximum edge-weighted clique problem ⋮ Refined pivot selection for maximal clique enumeration in graphs ⋮ An improved bit parallel exact maximum clique algorithm ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Finding the most degree-central walks and paths in a graph: exact and heuristic approaches ⋮ Combinatorial algorithms for the maximum \(k\)-plex problem ⋮ On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs ⋮ Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications ⋮ Improvements to MCS algorithm for the maximum clique problem ⋮ Multi-threading a state-of-the-art maximum clique algorithm ⋮ An effective branch-and-bound algorithm for the maximum \(s\)-bundle problem ⋮ On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs ⋮ Speeding up branch and bound algorithms for solving the maximum clique problem ⋮ A new upper bound for the maximum weight clique problem ⋮ A new branch-and-bound algorithm for the maximum weighted clique problem ⋮ An analytical comparison of the LP relaxations of integer models for the \(k\)-club problem ⋮ Cliques with maximum/minimum edge neighborhood and neighborhood density ⋮ Relaxed approximate coloring in exact maximum clique search ⋮ Upper bounds and heuristics for the 2-club problem ⋮ An exact bit-parallel algorithm for the maximum clique problem ⋮ Potential energy principles in networked systems and their connections to optimization problems on graphs ⋮ Detecting a most closeness-central clique in complex networks ⋮ Algorithms for finding maximum transitive subtournaments ⋮ An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph ⋮ Distance-Based Clique Relaxations in Networks: s-Clique and s-Club ⋮ An analysis of parameter adaptation in reactive tabu search ⋮ Reactive and dynamic local search for max-clique: engineering effective building blocks ⋮ Isolation concepts for clique enumeration: comparison and computational experiments ⋮ Algorithms for the generalized independent set problem based on a quadratic optimization approach ⋮ Enumerating Isolated Cliques in Synthetic and Financial Networks ⋮ An integer programming approach for finding the most and the least central cliques

Uses Software

• DIMACS
• CLIP
• Algorithm 457

Cites Work

• Selected combinatorial problems of computational biology
• Finding maximum cliques in arbitrary and in special graphs
• An exact algorithm for the maximum clique problem
• On probe interval graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• The algorithmics of folding proteins on lattices.
• Approximate protein folding in the HP side chain model on extended cubic lattices
• The haplotyping problem: an overview of computational models and solutions
• Opportunities for Combinatorial Optimization in Computational Biology
• Estimating the size of correcting codes using extremal graph problems
• Bioinformatics and Management Science: Some Common Tools and Techniques
• Finding a Maximum Clique in an Arbitrary Graph
• Algorithm 457: finding all cliques of an undirected graph
• On cliques in graphs
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Clique-detection models in computational biochemistry and genomics