Maximum weighted induced forests and trees: new formulations and a computational comparative review

DOI10.1111/itor.13066arXiv2102.09194OpenAlexW3210319024MaRDI QIDQ6071056

Rafael A. Melo, Celso Carneiro Ribeiro

Publication date: 27 November 2023

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

Full work available at URL: https://arxiv.org/abs/2102.09194

zbMATH Keywords

combinatorial optimizationmixed integer programminginduced subgraphsbranch-and-cutfeedback vertex set

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem
• Lower and upper bounds for the spanning tree with minimum branch vertices
• The three-in-a-tree problem
• A new branch-and-cut approach for the generalized regenerator location problem
• Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach
• Finding induced trees
• Large induced trees in \(K_r\)-free graphs
• A linear time algorithm for the minimum weighted feedback vertex set on diamonds
• Maximum induced trees in graphs
• Size bounds for dynamic monopolies
• The \(k\)-regular induced subgraph problem
• The rainbow spanning forest problem
• Solving the feedback vertex set problem on undirected graphs
• On exact solution approaches for the longest induced path problem
• 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
• An experimental study of ILP formulations for the longest induced path problem
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices
• Deadlock resolution in wait-for graphs by vertex/arc deletion
• Dominating and large induced trees in regular graphs
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Wavelength Conversion in Optical Networks
• On the maximum orders of an induced forest, an induced tree, and a stable set
• Rooted induced trees in triangle-free graphs
• A Tabu Search Heuristic Based on k-Diamonds for the Weighted Feedback Vertex Set Problem
• Integer Programming Formulation of Traveling Salesman Problems
• Feedback vertex sets and cyclically reducible graphs
• A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Decycling graphs
• Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Large Induced Forests in Graphs
• Exact and approximate algorithms for the longest induced path problem
• Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints
• The Maximum Weight Connected Subgraph Problem
• A linear programming based approach to the Steiner tree problem with a fixed number of terminals
• Computational comparisons of different formulations for the Stackelberg minimum spanning tree game

This page was built for publication: Maximum weighted induced forests and trees: new formulations and a computational comparative review