Open AccessOn fast path‐finding algorithms in AND‐OR graphs
Author(s) -
George M. Adelson-Velsky,
Alexander Gelbukh,
Eugene Levner
Publication year - 2002
Publication title -
mathematical problems in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.262
H-Index - 62
eISSN - 1026-7077
pISSN - 1024-123X
DOI - 10.1080/10241230306728
Subject(s) - longest path problem , path (computing) , time complexity , algorithm , computer science , mathematics , combinatorics , graph , chordal graph , programming language
We present a polynomial-time path-finding algorithm in AND-OR graphs Given p arcs and n nodes, the complexity of the algorithm is O(np), which is superior to the complexity of previously known algorithms
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom