@article{c6c5940bd69d43a7b379c3546375f86f,
title = "On fast path-finding algorithms in AND-OR graphs",
abstract = "A mathematical programming problem with min-max inequalities that is reduced to finding extremal paths in AND-OR graphs is addressed. A polynomial-time path-finding algorithm in AND-OR graphs is presented. Given p arcs and n nodes, the complexity of the algorithm is O(np), which is superior to the complexity of previously known algorithms.",
keywords = "AND-OR graphs, Extremal paths, Polynomial-time algorithms, Routing, Scheduling",
author = "Adelson-Velsky, {George M.} and Alexander Gelbukh and Eugene Levner",
note = "Funding Information: Adelson-Velsky George M. velsky@macs.biu.ac.il 1 Gelbukh Alexander gelbukh@cic.ipn.mx 2 Levner Eugene levner@hait.ac.il 3 1 Department of Mathematics and Computer Science Bar-Ilan University Ramat Gan Israel biu.ac.il 2 Center for Computing Research National Polytechnic Institute Mexico city Mexico 3 Department of Computer Science Holon Institute of Technology Holon Israel hit.ac.il 2002 8 4-5 283 293 07 02 2002 06 06 2002 2002 Copyright {\textcopyright} 2002 This is an open access article distributed under the Creative Commons Attribution License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. 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 ( n p ) , which is superior to the complexity of previously known algorithms. AND-OR graphs; Extremal paths; Scheduling; Routing; Polynomial-time algorithms http://dx.doi.org/10.13039/501100001738 Ministry of Science,Technology and space 98051-98 http://dx.doi.org/10.13039/501100003141 Consejo Nacional de Ciencia y Tecnolog{\'i}a ",
year = "2002",
month = sep,
doi = "10.1080/10241230306728",
language = "Ingl{\'e}s",
volume = "8",
pages = "283--293",
journal = "Mathematical Problems in Engineering",
issn = "1024-123X",
number = "4-5",
}