Maximum weighted induced forests and trees: new formulations and a computational comparative review (Q6071056): Difference between revisions

Latest revision as of 18:10, 30 December 2024

scientific article; zbMATH DE number 7771143

Language	Label	Description	Also known as
English	Maximum weighted induced forests and trees: new formulations and a computational comparative review	scientific article; zbMATH DE number 7771143

Statements

instance of

scholarly article

0 references

title

Maximum weighted induced forests and trees: new formulations and a computational comparative review (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

27 November 2023

0 references

full work available at URL

https://arxiv.org/abs/2102.09194

0 references

zbMATH Keywords

combinatorial optimization

0 references

mixed integer programming

0 references

branch-and-cut

0 references

induced subgraphs

0 references

feedback vertex set

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

The \(k\)-regular induced subgraph problem

0 references

The Maximum Weight Connected Subgraph Problem

0 references

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

0 references

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

0 references

Decycling graphs

0 references

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

0 references

Solving the feedback vertex set problem on undirected graphs

0 references

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

0 references

The rainbow spanning forest problem

0 references

Lower and upper bounds for the spanning tree with minimum branch vertices

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

Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach

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

Finding induced trees

0 references

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

0 references

Q5624995

0 references

Maximum induced trees in graphs

0 references

Q3145802

0 references

Large induced trees in \(K_r\)-free graphs

0 references

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

0 references

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

0 references

Wavelength Conversion in Optical Networks

0 references

Computational comparisons of different formulations for the Stackelberg minimum spanning tree game

0 references

A new branch-and-cut approach for the generalized regenerator location problem

0 references

An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem

0 references

Q4845371

0 references

A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem

0 references

Exact and approximate algorithms for the longest induced path problem

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

An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices

0 references

Integer Programming Formulation of Traveling Salesman Problems

0 references

Size bounds for dynamic monopolies

0 references

Rooted induced trees in triangle-free graphs

0 references

Dominating and large induced trees in regular graphs

0 references

Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem

0 references

Q3129824

0 references

A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs

0 references

Large Induced Forests in Graphs

0 references

A linear programming based approach to the Steiner tree problem with a fixed number of terminals

0 references

Feedback vertex sets and cyclically reducible graphs

0 references

Identifiers

arXiv ID

2102.09194

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6071056

@@ Property / DOI @@
-.1111/itor.13066
@@ Property / DOI: 10.1111/itor.13066 / rank @@
-Normal rank
@@ Property / OpenAlex ID @@
+W3210319024
@@ Property / OpenAlex ID: W3210319024 / rank @@
+Normal rank
@@ Property / cites work @@
+The \(k\)-regular induced subgraph problem
@@ Property / cites work: The \(k\)-regular induced subgraph problem / rank @@
+Normal rank
@@ Property / cites work @@
+The Maximum Weight Connected Subgraph Problem
@@ Property / cites work: The Maximum Weight Connected Subgraph Problem / rank @@
+Normal rank
@@ Property / cites work @@
+A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
+Normal rank
@@ Property / cites work @@
+Decycling graphs
@@ Property / cites work: Decycling graphs / rank @@
+Normal rank
@@ Property / cites work @@
+An experimental study of ILP formulations for the longest induced path problem
+Normal rank
@@ Property / cites work @@
+Solving the feedback vertex set problem on undirected graphs
+Normal rank
@@ Property / cites work @@
+Deadlock resolution in wait-for graphs by vertex/arc deletion
+Normal rank
@@ Property / cites work @@
+The rainbow spanning forest problem
@@ Property / cites work: The rainbow spanning forest problem / rank @@
+Normal rank
@@ Property / cites work @@
+Lower and upper bounds for the spanning tree with minimum branch vertices
+Normal rank
@@ Property / cites work @@
+A linear time algorithm for the minimum weighted feedback vertex set on diamonds
+Normal rank
@@ Property / cites work @@
+A Tabu Search Heuristic Based on k-Diamonds for the Weighted Feedback Vertex Set Problem
+Normal rank
@@ Property / cites work @@
+Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach
+Normal rank
@@ Property / cites work @@
+The three-in-a-tree problem
@@ Property / cites work: The three-in-a-tree problem / rank @@
+Normal rank
@@ Property / cites work @@
+Q3651735
@@ Property / cites work: Q3651735 / rank @@
+Normal rank
@@ Property / cites work @@
+Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints
+Normal rank
@@ Property / cites work @@
+Finding induced trees
@@ Property / cites work: Finding induced trees / rank @@
+Normal rank
@@ Property / cites work @@
+Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
+Normal rank
@@ Property / cites work @@
+Q5624995
@@ Property / cites work: Q5624995 / rank @@
+Normal rank
@@ Property / cites work @@
+Maximum induced trees in graphs
@@ Property / cites work: Maximum induced trees in graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3145802
@@ Property / cites work: Q3145802 / rank @@
+Normal rank
@@ Property / cites work @@
+Large induced trees in \(K_r\)-free graphs
@@ Property / cites work: Large induced trees in \(K_r\)-free graphs / rank @@
+Normal rank
@@ Property / cites work @@
+High multiplicity asymmetric traveling salesman problem with feedback vertex set and its application to storage/retrieval system
+Normal rank
@@ Property / cites work @@
+On the maximum orders of an induced forest, an induced tree, and a stable set
+Normal rank
@@ Property / cites work @@
+Wavelength Conversion in Optical Networks
@@ Property / cites work: Wavelength Conversion in Optical Networks / rank @@
+Normal rank
@@ Property / cites work @@
+Computational comparisons of different formulations for the Stackelberg minimum spanning tree game
+Normal rank
@@ Property / cites work @@
+A new branch-and-cut approach for the generalized regenerator location problem
+Normal rank
@@ Property / cites work @@
+An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
+Normal rank
@@ Property / cites work @@
+Q4845371
@@ Property / cites work: Q4845371 / rank @@
+Normal rank
@@ Property / cites work @@
+A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem
+Normal rank
@@ Property / cites work @@
+Exact and approximate algorithms for the longest induced path problem
+Normal rank
@@ Property / cites work @@
+On exact solution approaches for the longest induced path problem
+Normal rank
@@ Property / cites work @@
+Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem
+Normal rank
@@ Property / cites work @@
+An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices
+Normal rank
@@ Property / cites work @@
+Integer Programming Formulation of Traveling Salesman Problems
+Normal rank
@@ Property / cites work @@
+Size bounds for dynamic monopolies
@@ Property / cites work: Size bounds for dynamic monopolies / rank @@
+Normal rank
@@ Property / cites work @@
+Rooted induced trees in triangle-free graphs
@@ Property / cites work: Rooted induced trees in triangle-free graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Dominating and large induced trees in regular graphs
+Normal rank
@@ Property / cites work @@
+Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem
+Normal rank
@@ Property / cites work @@
+Q3129824
@@ Property / cites work: Q3129824 / rank @@
+Normal rank
@@ Property / cites work @@
+A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
+Normal rank
@@ Property / cites work @@
+Large Induced Forests in Graphs
@@ Property / cites work: Large Induced Forests in Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A linear programming based approach to the Steiner tree problem with a fixed number of terminals
+Normal rank
@@ Property / cites work @@
+Feedback vertex sets and cyclically reducible graphs
+Normal rank
@@ Property / DOI @@
+.1111/ITOR.13066
@@ Property / DOI: 10.1111/ITOR.13066 / rank @@
+Normal rank