MIP formulations for induced graph optimization problems: a tutorial (Q6056886)

scientific article; zbMATH DE number 7745324

Language	Label	Description	Also known as
English	MIP formulations for induced graph optimization problems: a tutorial	scientific article; zbMATH DE number 7745324

Statements

instance of

scholarly article

0 references

title

MIP formulations for induced graph optimization problems: a tutorial (English)

0 references

author

Rafael A. Melo

0 references

Celso Carneiro Ribeiro

0 references

published in

International Transactions in Operational Research

0 references

publication date

4 October 2023

0 references

zbMATH Keywords

combinatorial optimization

0 references

integer programming

0 references

induced graphs

0 references

feedback vertex set

0 references

induced paths

0 references

quasi-cliques

0 references

networks

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1111/itor.13299

0 references

cites work

Q3044359

0 references

The $k$-regular induced subgraph problem

0 references

A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem

0 references

A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives

0 references

Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference

0 references

Emergence of Scaling in Random Networks

0 references

Decycling graphs

0 references

Fast exact algorithms for some connectivity problems parameterized by clique-width

0 references

More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints

0 references

On the complexity of testing for odd holes and induced odd paths

0 references

An experimental study of ILP formulations for the longest induced path problem

0 references

Q3145799

0 references

Three-coloring and list three-coloring of graphs without induced paths on seven vertices

0 references

Algorithm 457: finding all cliques of an undirected graph

0 references

Solving the feedback vertex set problem on undirected graphs

0 references

The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel

0 references

Induced matchings

0 references

Q3439702

0 references

Cliques, holes and the vertex coloring polytope

0 references

On feedback vertex set: new measure and new structures

0 references

Deadlock resolution in wait-for graphs by vertex/arc deletion

0 references

A linear time algorithm for the minimum weighted feedback vertex set on diamonds

0 references

A Tabu Search Heuristic Based on k-Diamonds for the Weighted Feedback Vertex Set Problem

0 references

A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs

0 references

Approximately coloring graphs without long induced paths

0 references

The three-in-a-tree problem

0 references

Q3651735

0 references

Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints

0 references

Q3835053

0 references

An $\mathcal O(2^{O(k)}n^{3})$ FPT algorithm for the undirected feedback vertex set problem

0 references

Finding induced trees

0 references

The four-in-a-tree problem in triangle-free graphs

0 references

Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints

0 references

A lower bound on the order of the largest induced forest in planar graphs with high girth

0 references

Large induced forests in planar graphs with girth 4

0 references

A lower bound on the order of the largest induced linear forest in triangle-free planar graphs

0 references

On the approximability of the maximum induced matching problem

0 references

On Induced Paths, Holes, and Trees in Random Graphs

0 references

Maximum induced trees in graphs

0 references

A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set

0 references

Q3145802

0 references

The $k$-in-a-path problem for claw-free graphs

0 references

Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$

0 references

On the minimum feedback vertex set problem: Exact and enumeration algorithms

0 references

Large induced trees in $K_r$-free graphs

0 references

Large induced trees in sparse random graphs

0 references

A branch-and-cut algorithm for partition coloring

0 references

Q4198056

0 references

Algorithms for maximum weight induced paths

0 references

Minimum weight feedback vertex sets in circle graphs

0 references

High multiplicity asymmetric traveling salesman problem with feedback vertex set and its application to storage/retrieval system

0 references

Compact structure for sparse undirected graphs based on a clique graph partition

0 references

A catalog of steiner tree formulations

0 references

Coloring graphs without short cycles and long induced paths

0 references

Induced disjoint paths in AT-free graphs

0 references

Induced Disjoint Paths in Claw-Free Graphs

0 references

Average distance and maximum induced forest

0 references

On the maximum orders of an induced forest, an induced tree, and a stable set

0 references

Snakes, coils, and single-track circuit codes with spread $k$

0 references

An improved algorithm for the longest induced path problem on $k$-chordal graphs

0 references

Mim-width. I. Induced path problems

0 references

Mim-width. II. The feedback vertex set problem

0 references

On approximating the longest path in a graph

0 references

Minimum size of feedback vertex sets of planar graphs of girth at least five

0 references

Wavelength Conversion in Optical Networks

0 references

Q4633929

0 references

Faster deterministic \textsc{Feedback Vertex Set}

0 references

Graph-Theoretic Concepts in Computer Science

0 references

Maximum induced forests in random graphs

0 references

Three-in-a-tree in near linear time

0 references

Detecting induced subgraphs

0 references

The $k$-in-a-tree problem for graphs of girth at least $k$

0 references

Some results on graphs without long induced paths

0 references

Q4845371

0 references

LP-based dual bounds for the maximum quasi-clique problem

0 references

New formulations and branch-and-cut procedures for the longest induced path problem

0 references

Exact and approximate algorithms for the longest induced path problem

0 references

Induced trees in triangle-free graphs

0 references

On exact solution approaches for the longest induced path problem

0 references

Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem

0 references

A matheuristic approach for the $b$-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic

0 references

Integer Programming Formulation of Traveling Salesman Problems

0 references

On cliques in graphs

0 references

Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs

0 references

On the order of the largest induced tree in a random graph

0 references

On the maximum quasi-clique problem

0 references

Size bounds for dynamic monopolies

0 references

Exact Solution Algorithms for the Chordless Cycle Problem

0 references

Rooted induced trees in triangle-free graphs

0 references

A BRKGA-based matheuristic for the maximum quasi-clique problem with an exact local search strategy

0 references

A biased random-key genetic algorithm for the maximum quasi-clique problem

0 references

Dominating and large induced trees in regular graphs

0 references

Exact Computation of Maximum Induced Forest

0 references

An exact algorithm for the maximum quasi‐clique problem

0 references

Q3129824

0 references

Finding influential communities in networks with multiple influence types

0 references

A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs

0 references

Large Induced Forests in Graphs

0 references

On large induced trees and long induced paths in sparse random graphs

0 references

Finding a Maximum Independent Set

0 references

The worst-case time complexity for generating all maximal cliques and computational experiments

0 references

Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs

0 references

Q5298938

0 references

Feedback vertex sets and cyclically reducible graphs

0 references

The maximum k-colorable subgraph problem for chordal graphs

0 references

Snake-in-the-Box Codes for Rank Modulation

0 references

An opposition-based memetic algorithm for the maximum quasi-clique problem

0 references

Identifiers

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6056886