On exact solution approaches for the longest induced path problem
From MaRDI portal
Publication:1999389
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
integer programmingnetworkslongest induced path problemmaximum subgraph identification problemrandomized heuristic
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
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