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

DOI10.1016/j.cor.2021.105627OpenAlexW3216275810MaRDI QIDQ2669795

Celso Carneiro Ribeiro, Ruslán G. Marzo, Marcio C. Santos, Rafael A. Melo

Publication date: 9 March 2022

Published in: Computers \& Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

integer programmingcombinatorial optimizationmaximum cardinalitylongest induced pathmaximum induced subgraphs

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Related Items (2)

MIP formulations for induced graph optimization problems: a tutorial ⋮ The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study

Uses Software

• Algorithm 457
• CPU Benchmarks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The worst-case time complexity for generating all maximal cliques and computational experiments
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• Some results on graphs without long induced paths
• Algorithms for maximum weight induced paths
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• The \(k\)-regular induced subgraph 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
• Mim-width. I. Induced path problems
• An experimental study of ILP formulations for the longest induced path problem
• Snakes, coils, and single-track circuit codes with spread \(k\)
• Exhaustive search for snake-in-the-box codes
• Coloring graphs without short cycles and long induced paths
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Snake-in-the-Box Codes for Rank Modulation
• A Tabu Search Heuristic Based on k-Diamonds for the Weighted Feedback Vertex Set Problem
• Emergence of Scaling in Random Networks
• Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem
• 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 catalog of steiner tree formulations
• Algorithm 457: finding all cliques of an undirected graph
• Graph-Theoretic Concepts in Computer Science
• Approximately coloring graphs without long induced paths
• On cliques in graphs

This page was built for publication: New formulations and branch-and-cut procedures for the longest induced path problem