On exact solution approaches for the longest induced path problem

DOI10.1016/j.ejor.2019.04.011zbMath1430.90547OpenAlexW2936539364MaRDI QIDQ1999389

Dmytro Matsypura, Alexander Veremyev, Oleg A. Prokopyev, Eduardo L. Pasiliao

Publication date: 26 June 2019

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2019.04.011

zbMATH Keywords

integer programmingnetworkslongest induced path problemmaximum subgraph identification problemrandomized heuristic

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Deterministic network models in operations research (90B10)

Related Items

New formulations and branch-and-cut procedures for the longest induced path problem, MIP formulations for induced graph optimization problems: a tutorial, Maximum weighted induced forests and trees: new formulations and a computational comparative review, The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study, Finding the most degree-central walks and paths in a graph: exact and heuristic approaches

Uses Software

• NetworkX
• Pajek
• Gurobi
• Pajek datasets
• SparseMatrix
• Matplotlib
• igraph
• DIMACS
• Anaconda

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• Lower and upper bounds for long induced paths in 3-connected planar graphs
• Finding maximum subgraphs with relatively large vertex connectivity
• Long induced paths in graphs
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• Mean distance in a graph
• Algorithms for maximum weight induced paths
• Linear time solvable optimization problems on graphs of bounded clique-width
• On clique relaxation models in network analysis
• The university of Florida sparse matrix collection
• Statistical mechanics of complex networks
• Emergence of Scaling in Random Networks
• Community structure in social and biological networks
• Networks
• Finding groups with maximum betweenness centrality
• Collective dynamics of ‘small-world’ networks