Exact and approximate algorithms for the longest induced path problem

DOI10.1051/RO/2021004MaRDI QIDQ5003500zbMATH OpenOpenAlexFDO

Authors Ruslán G. Marzo, Celso C. Ribeiro

Publication date 22 July 2021

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1051/ro/2021004

zbMATH Keywords

heuristicsexact algorithmbacktrackinglongest induced path problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25) Distance in graphs (05C12) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Recommendations

• On exact solution approaches for the longest induced path problem
• An experimental study of ILP formulations for the longest induced path problem
• New formulations and branch-and-cut procedures for the longest induced path problem
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• On computing longest paths in small graph classes

Cited in

(11)

• An experimental study of ILP formulations for the longest induced path problem
• Exact approaches for the orderly colored longest path problem: performance comparison
• On approximating the longest path in a graph
• 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
• Maximum weighted induced forests and trees: new formulations and a computational comparative review
• Algorithms for maximum weight induced paths
• On exact solution approaches for the longest induced path problem
• New formulations and branch-and-cut procedures for the longest induced path problem
• Exact methods for solving the elementary shortest and longest path problems

This page was built for publication: Exact and approximate algorithms 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 Q5003500)