MIP formulations for induced graph optimization problems: a tutorial

DOI10.1111/itor.13299OpenAlexW4366287454MaRDI QIDQ6056886

Rafael A. Melo, Celso Carneiro Ribeiro

Publication date: 4 October 2023

Published in: International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1111/itor.13299

zbMATH Keywords

integer programmingcombinatorial optimizationnetworksfeedback vertex setinduced pathsinduced graphsquasi-cliques

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites Work

• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• A lower bound on the order of the largest induced forest in planar graphs with high girth
• On feedback vertex set: new measure and new structures
• A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• The three-in-a-tree problem
• On approximating the longest path in a graph
• Minimum size of feedback vertex sets of planar graphs of girth at least five
• The four-in-a-tree problem in triangle-free graphs
• The worst-case time complexity for generating all maximal cliques and computational experiments
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Minimum weight feedback vertex sets in circle graphs
• Finding induced trees
• Large induced trees in \(K_r\)-free graphs
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• Some results on graphs without long induced paths
• Cliques, holes and the vertex coloring polytope
• A linear time algorithm for the minimum weighted feedback vertex set on diamonds
• Maximum induced trees in graphs
• On the order of the largest induced tree in a random graph
• The maximum k-colorable subgraph problem for chordal graphs
• On the complexity of testing for odd holes and induced odd paths
• On large induced trees and long induced paths in sparse random graphs
• Induced matchings
• Size bounds for dynamic monopolies
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Algorithms for maximum weight induced paths
• A biased random-key genetic algorithm for the maximum quasi-clique problem
• Large induced forests in planar graphs with girth 4
• A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
• On the maximum quasi-clique problem
• On the approximability of the maximum induced matching problem
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• The \(k\)-regular induced subgraph problem
• Large induced trees in sparse random graphs
• Solving the feedback vertex set problem on undirected graphs
• On exact solution approaches for the longest induced path problem
• Faster deterministic \textsc{Feedback Vertex Set}
• Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem
• High multiplicity asymmetric traveling salesman problem with feedback vertex set and its application to storage/retrieval system
• Induced disjoint paths in AT-free graphs
• Compact structure for sparse undirected graphs based on a clique graph partition
• Finding influential communities in networks with multiple influence types
• Mim-width. I. Induced path problems
• An opposition-based memetic algorithm for the maximum quasi-clique problem
• An experimental study of ILP formulations for the longest induced path problem
• Maximum induced forests in random graphs
• A matheuristic approach for the \(b\)-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Mim-width. II. The feedback vertex set problem
• Snakes, coils, and single-track circuit codes with spread \(k\)
• Fast exact algorithms for some connectivity problems parameterized by clique-width
• Deadlock resolution in wait-for graphs by vertex/arc deletion
• The \(k\)-in-a-path problem for claw-free graphs
• Coloring graphs without short cycles and long induced paths
• Dominating and large induced trees in regular graphs
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• LP-based dual bounds for the maximum quasi-clique problem
• New formulations and branch-and-cut procedures for the longest induced path problem
• Wavelength Conversion in Optical Networks
• On the maximum orders of an induced forest, an induced tree, and a stable set
• Snake-in-the-Box Codes for Rank Modulation
• Rooted induced trees in triangle-free graphs
• A branch-and-cut algorithm for partition coloring
• A Tabu Search Heuristic Based on k-Diamonds for the Weighted Feedback Vertex Set Problem
• Emergence of Scaling in Random Networks
• Integer Programming Formulation of Traveling Salesman Problems
• Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• Average distance and maximum induced forest
• Feedback vertex sets and cyclically reducible graphs
• A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
• Finding a Maximum Independent Set
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• Decycling graphs
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Large Induced Forests in Graphs
• A BRKGA-based matheuristic for the maximum quasi-clique problem with an exact local search strategy
• Exact and approximate algorithms for the longest induced path problem
• More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
• Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs
• Exact Solution Algorithms for the Chordless Cycle Problem
• Three-in-a-tree in near linear time
• Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints
• Induced Disjoint Paths in Claw-Free Graphs
• A catalog of steiner tree formulations
• Algorithm 457: finding all cliques of an undirected graph
• Exact Computation of Maximum Induced Forest
• On Induced Paths, Holes, and Trees in Random Graphs
• Detecting induced subgraphs
• Induced trees in triangle-free graphs
• Graph-Theoretic Concepts in Computer Science
• Approximately coloring graphs without long induced paths
• On cliques in graphs
• An exact algorithm for the maximum quasi‐clique problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: MIP formulations for induced graph optimization problems: a tutorial