An algebraic approach to the longest path problem

DOI10.1016/J.TCS.2025.115590MaRDI QIDQ6891668zbMATH OpenFDO

Authors Omar Al - Khazali

Publication date 2 December 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115590

zbMATH Keywords

algebraic graph theorylongest path problem

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Review text

It is known that the longest path problem (LPP) is a big challenge in combinatorial optimization as it is linked to the Hamiltonian Path Problem (HPP). The authors in this article come up with a new technique called Booleanisation and manage to find the longest paths for several well-known classes of graphs, such as tree-like classes of graphs, by developing algorithms that belong to the class P. The methods introduced here produce any path of any length.

Cites work

• A note on two problems in connexion with graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Faster matrix multiplication via asymmetric hashing
• On computing a longest path in a tree
• On the shortest spanning subtree of a graph and the traveling salesman problem
• The longest path problem is polynomial on cocomparability graphs
• The Longest Path Problem Is Polynomial on Interval Graphs
• The orderly colored longest path problem -- a survey of applications and new algorithms

This page was built for publication: An algebraic approach to the longest path problem

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