Free Access
RAIRO-Oper. Res.
Volume 55, Number 2, March-April 2021
Page(s) 333 - 353
Published online 23 March 2021
  • R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network flows. Elsevier (1988). [Google Scholar]
  • P. Alles and S. Poljak, Long induced paths and cycles in Kneser graphs. Graphs Comb. 5 (1989) 303–306. [Google Scholar]
  • A.-L. Barabási and R. Albert, Emergence of scaling in random networks. Science 286 (1999) 509–512. [Google Scholar]
  • B. Bergougnoux and M.M. Kanté, A meta-algorithm for solving connectivity and acyclicity constraints on locally checkable properties parameterized by graph width measures. Preprint arXiv:1805.11275 (2018). [Google Scholar]
  • F. Bökler, M. Chimani, M.H. Wagner and T. Wiedera, An experimental study of ILP formulations for the longest induced path problem. In Combinatorial Optimization, edited by M. Baïou, B. Gendron, O. Günlük and A.R. Mahjoub. In Vol. 12176 of Lecture Notes in Computer Science. Springer, Cham (2020). [Google Scholar]
  • M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman and Co., New York (1979). [Google Scholar]
  • F. Gavril, Algorithms for maximum weight induced paths. Inf. Process. Lett. 81 (2002) 203–208. [Google Scholar]
  • T. Ishizeki, Y. Otachi and K. Yamazaki, An improved algorithm for the longest induced path problem on k-chordal graphs. Discrete Appl. Math. 156 (2008) 3057–3059. [Google Scholar]
  • L. Jaffke, O.-J. Kwon and J. Telle, Polynomial-time algorithms for the Longest Induced Path and Induced Disjoint Paths problems on graphs of bounded mim-width. In: Vol. 89 of Leibniz International Proceedings in Informatics (2018) 1–21. [Google Scholar]
  • L. Jaffke, O.-J. Kwon and J.A. Telle, Mim-Width I. Induced path problems. Discrete Appl. Math. 278 (2020) 153–168. [Google Scholar]
  • W.H. Kautz, Unit-Distance Error-Checking Codes. IRE Trans. Electron. Comput. 7 (1958) 179–180. [Google Scholar]
  • D. Kratsch, H. Müller and I. Todinca, Feedback vertex set and longest induced path on AT-free graphs. In: International Workshop on Graph-Theoretic Concepts in Computer Science. Springer (2003) 309–321. [Google Scholar]
  • D. Matsypura, A. Veremyev, O.A. Prokopyev and E.L. Pasiliao, On exact solution approaches for the longest induced path problem. Eur. J. Oper. Res. 278 (2019) 546–562. [Google Scholar]
  • Moviegalaxies, Social networks in movies. Available from: (2020). [Google Scholar]
  • NetworkX developers, NetworkX documentation. Available from: [Google Scholar]
  • M.E. Newman, The structure and function of complex networks. SIAM Rev. 45 (2003) 167–256. [Google Scholar]
  • PassMark, PassMark Software – CPU Benchmarks. Intel Core i5-4460S vs. Intel Xeon E5-1650 v2 vs. Intel Xeon Gold 6134. Available from: (2020). [Google Scholar]
  • K. Pearson, Notes on regression and inheritance in the case of two parents. Proc. R. Soc. London 58 (1895) 240–242. [Google Scholar]
  • L.O. Prokhorenkova and E. Samosvat, Global clustering coefficient in scale-free networks. In: International Workshop on Algorithms and Models for the Web-Graph. Springer (2014) 47–58. [Google Scholar]
  • D.J. Watts and S.H. Strogatz, Collective dynamics of ``small-world’’ networks. Nature 393 (1998) 440–442. [CrossRef] [PubMed] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.