MIP formulations for induced graph optimization problems: a tutorial
From MaRDI portal
Publication:6056886
Cites work
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A biased random-key genetic algorithm for the maximum quasi-clique problem
- A branch-and-cut algorithm for partition coloring
- A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
- A BRKGA-based matheuristic for the maximum quasi-clique problem with an exact local search strategy
- A catalog of steiner tree formulations
- A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
- A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
- A linear time algorithm for the minimum weighted feedback vertex set on diamonds
- A lower bound on the order of the largest induced forest in planar graphs with high girth
- A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
- A matheuristic approach for the \(b\)-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- A tabu search heuristic based on k-diamonds for the weighted feedback vertex set problem
- Algorithm 457: finding all cliques of an undirected graph
- Algorithms for finding an induced cycle in planar graphs and bounded genus graphs
- Algorithms for maximum weight induced paths
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
- An exact algorithm for the maximum quasi‐clique problem
- An experimental study of ILP formulations for the longest induced path problem
- An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
- An opposition-based memetic algorithm for the maximum quasi-clique problem
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Average distance and maximum induced forest
- Cliques, holes and the vertex coloring polytope
- Coloring graphs without short cycles and long induced paths
- Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem
- Compact structure for sparse undirected graphs based on a clique graph partition
- Deadlock resolution in wait-for graphs by vertex/arc deletion
- Decycling graphs
- Dominating and large induced trees in regular graphs
- Emergence of Scaling in Random Networks
- Exact and approximate algorithms for the longest induced path problem
- Exact Computation of Maximum Induced Forest
- Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
- Exact Solution Algorithms for the Chordless Cycle Problem
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- Faster deterministic \textsc{Feedback Vertex Set}
- Feedback vertex set and even cycle transversal for H-free graphs: finding large block graphs
- Feedback vertex sets and cyclically reducible graphs
- Finding a Maximum Independent Set
- Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
- Finding induced trees
- Finding influential communities in networks with multiple influence types
- Graph-Theoretic Concepts in Computer Science
- High multiplicity asymmetric traveling salesman problem with feedback vertex set and its application to storage/retrieval system
- scientific article; zbMATH DE number 2086259 (Why is no real title available?)
- scientific article; zbMATH DE number 1002021 (Why is no real title available?)
- scientific article; zbMATH DE number 6118217 (Why is no real title available?)
- scientific article; zbMATH DE number 6118220 (Why is no real title available?)
- scientific article; zbMATH DE number 5158521 (Why is no real title available?)
- scientific article; zbMATH DE number 4112072 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 795222 (Why is no real title available?)
- Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
- Induced disjoint paths in claw-free graphs
- Induced matchings
- Induced trees in triangle-free graphs
- Integer Programming Formulation of Traveling Salesman Problems
- Introduction to algorithms.
- Large induced forests in graphs
- Large induced forests in planar graphs with girth 4
- Large induced trees in \(K_r\)-free graphs
- Large induced trees in sparse random graphs
- LP-based dual bounds for the maximum quasi-clique problem
- Maximum induced forests in random graphs
- Maximum induced trees in graphs
- Mim-width. I. Induced path problems
- Mim-width. II. The feedback vertex set problem
- Minimum size of feedback vertex sets of planar graphs of girth at least five
- Minimum weight feedback vertex sets in circle graphs
- Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints
- More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
- Network clustering via clique relaxation: a community based approach
- New formulations and branch-and-cut procedures for the longest induced path problem
- On approximating the longest path in a graph
- On cliques in graphs
- On exact solution approaches for the longest induced path problem
- On feedback vertex set: new measure and new structures
- On Induced Paths, Holes, and Trees in Random Graphs
- On large induced trees and long induced paths in sparse random graphs
- On the approximability of the maximum induced matching problem
- On the complexity of testing for odd holes and induced odd paths
- On the maximum orders of an induced forest, an induced tree, and a stable set
- On the maximum quasi-clique problem
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- On the order of the largest induced tree in a random graph
- Rooted induced trees in triangle-free graphs
- Size bounds for dynamic monopolies
- Snake-in-the-Box Codes for Rank Modulation
- Snakes, coils, and single-track circuit codes with spread \(k\)
- Solving the feedback vertex set problem on undirected graphs
- Some results on graphs without long induced paths
- The \(k\)-in-a-path problem for claw-free graphs
- The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
- The k-regular induced subgraph problem
- The four-in-a-tree problem in triangle-free graphs
- The maximum k-colorable subgraph problem for chordal graphs
- The three-in-a-tree problem
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- The worst-case time complexity for generating all maximal cliques and computational experiments
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Three-in-a-tree in near linear time
- Wavelength conversion in optical networks
Cited in
(5)- Semidefinite programming bounds and a branch-and-bound algorithm for the chordless cycle problem
- The connected Grundy coloring problem: formulations and a local-search enhanced biased random-key genetic algorithm
- Local-MIP: efficient local search for mixed integer programming
- A biased random-key genetic algorithm for the minimum quasi-clique partitioning problem
- Obtaining the Grundy chromatic number: how bad can my greedy heuristic coloring be?
This page was built for publication: MIP formulations for induced graph optimization problems: a tutorial
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6056886)
