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

DOI10.1016/J.COR.2021.105627OpenAlexW3216275810MaRDI QIDQ2669795FDOQ2669795

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

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

Recommendations

• An experimental study of ILP formulations for the longest induced path problem
• Exact and approximate algorithms for the longest induced path problem
• On exact solution approaches for the longest induced path problem
• Exact approaches for the orderly colored longest path problem: performance comparison
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs

zbMATH Keywords

combinatorial optimizationinteger programmingmaximum cardinalitylongest induced pathmaximum induced subgraphs

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Cites Work

• Algorithm 457: finding all cliques of an undirected graph
• Emergence of Scaling in Random Networks
• Introduction to algorithms.
• Title not available (Why is that?)
• The \(k\)-regular induced subgraph problem
• On cliques in graphs
• Some results on graphs without long induced paths
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• Algorithms for maximum weight induced paths
• Graph-Theoretic Concepts in Computer Science
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Title not available (Why is that?)
• Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints
• The worst-case time complexity for generating all maximal cliques and computational experiments
• Coloring graphs without short cycles and long induced paths
• A catalog of steiner tree formulations
• Title not available (Why is that?)
• Snake-in-the-Box Codes for Rank Modulation
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Solving the feedback vertex set problem on undirected graphs
• The Maximum Weight Connected Subgraph Problem
• On exact solution approaches for the longest induced path problem
• Exact and approximate algorithms for the longest induced path problem
• A tabu search heuristic based on \(k\)-diamonds for the weighted feedback vertex set problem
• An experimental study of ILP formulations for the longest induced path problem
• Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem
• Snakes, coils, and single-track circuit codes with spread \(k\)
• Mim-width. I. Induced path problems
• Combining NP-hard reduction techniques and strong heuristics in an exact algorithm for the maximum-weight connected subgraph problem
• Exhaustive search for snake-in-the-box codes

Cited In (9)

• Exact and approximate algorithms for the longest induced path problem
• An experimental study of ILP formulations for the longest induced path problem
• MIP formulations for induced graph optimization problems: a tutorial
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• Exact methods for the longest induced cycle problem
• New formulations and branch-and-cut procedures for the longest induced path problem
• On exact solution approaches for the longest induced path problem
• Integer programming formulations for the \(k\)-in-a-tree problem in graphs
• The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study

Uses Software

• Algorithm 457
• CPU Benchmarks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2669795)