% BibTeX database kpath.bib % exported by BibGene 1.2.2, Mon, Mar 19, 2001. % Bibliography on k shortest paths and other "k best solutions" problems % David Eppstein, Univ. of Calif., Irvine, Dept. Information & Computer Sci., % http://www.ics.uci.edu/~eppstein/ @phdthesis{Abd-PhD-88, title = {{A Dual-Based Approach to a Multiobjective Location Problem}}, author = {Bahgat Abdel-Hameed Abdel-Lateef}, school = {Univ. of Liverpool, Dept. of Mathematics}, year = {1988}, abstract = {The work presented in this thesis is concerned with the use of dual-based approaches for solving Multi-objective Location Problems which may be used to represent many real life location Problems. In particular, attention is directed towards the use of Lagrangean relaxation. The Multi-objective problem to which most effort is devoted here is the Maximum Covering Shortest Path (MCSP) problem. MCSP seeks a path in a network, from starting (source) node to terminus (sink) node, which is simultaneously as short as possible and covers the maximum population (by passing within a 'covering distance'). Our approach differs from the existing one, based on use of a general integer programming package, using a Lagrangean relaxation approach instead. The subproblems generated are simple shortest route problems relative to reduced arc lengths. This avoids the difficulty of 'isolated circuits' (subtours) encountered previously. On the other hand, care has to be taken to prevent the occurrence of negative length circuits (relative to reduced arc lengths). Some experimental results are presented. Subgradient optimisation is used for the Lagrangean dual problem. A branch-and bound algorithm is also implemented for closing any duality gap (which may result from the integrality constraints). Our approach to MCSP also uses K-shortest path, and a suitable algorithm for this is devised. The new method called Anticipatory Nemhauser, is presented together with the data structures used and shown to be very promising in terms of computation time required. The other problems, considered briefly, are the Hierarchical Network Design Problem (HNDP) and the Median Shortest Path Problem (MSPP). For the first of these a dual-based scheme is developed and applied to an example with considerable success but further experimentation is required to establish the merits of our approach more generally. The relationship between MSPP and HNDP is considered. Finally, the last chapter presents our conclusions and suggestion for further work.}} @inproceedings{AggSchTok-SCG-93, title = {{Finding a minimum weight $K$-link path in graphs with Monge property and applications}}, author = {Alok Aggarwal and Baruch Schieber and T. Tokuyama}, booktitle = {Proc. 9th Symp. Computational Geometry}, publisher = {ACM}, pages = {189--197}, year = {1993}} @article{AhuMehOrl-JACM-90, title = {{Faster algorithms for the shortest path problem}}, author = {Ravindra K. Ahuja and Kurt Mehlhorn and James B. Orlin and Robert E. Tarjan}, journal = {J. Assoc. Comput. Mach.}, publisher = {ACM}, volume = {37}, pages = {213--223}, year = {1990}} @techreport{AhuMehOrl-TR-88, title = {{Faster algorithms for the shortest path problem}}, author = {Ravindra K. Ahuja and Kurt Mehlhorn and James B. Orlin and Robert E. Tarjan}, institution = {MIT Operations Research Ctr.}, number = {193}, year = {1988}} @article{Aih-ECJ-75, title = {{An approach to enumerating elementary paths and cutsets by Gaussian elimination method}}, author = {K. Aihara}, journal = {Electronics and Communications in Japan}, volume = {58}, number = {1}, pages = {1--10}, year = {1975}, abstract = {Discusses a new method of enumerating elementary paths and cutsets for all node pairs in a graph by means of Gaussian elimination. Elimination of elementary paths and cutsets is very important from the viewpoint of graph theory as well as network theory. In the past, the combinatorial method and the algebraic approach have been discussed independently although both are impractical.}} @article{Alt-ICCA-97, title = {{On the K-best mode in computer chess: measuring the similarity of move proposals}}, author = {Ingo Alth{\"o}fer}, journal = {ICCA J.}, volume = {20}, number = {3}, pages = {152--165}, month = {September}, year = {1997}} @techreport{Alt-TR-99, title = {{Decision Support Systems With Multiple Choice Structure}}, author = {Ingo Alth{\"o}fer}, type = {Jenaer Schriften zur Mathematik und Informatik}, address = {D-07740 Jena, GERMANY}, institution = {Friedrich-Schiller-Univ. Jena, Fakult{\"a}t f{\"u}r Mathematik und Informatik}, number = {99-31}, month = {June}, year = {1999}, url = {http://www.minet.uni-jena.de/Math-Net/reports/shadows//99-31report.html}} @article{AltWen-AAM-99, title = {{Two-best solutions under distance constraints: the model and exemplary results for matroids}}, author = {Ingo Alth{\"o}fer and Walter Wenzel}, journal = {Advances in Applied Math.}, volume = {22}, number = {2}, pages = {155--185}, month = {February}, year = {1999}, abstract = {In discrete maximization problems one typically wants to find an optimal solution. However, in topics like ``alignment of DNA-strings,'' ``automatic speech recognition,'' and ``computer chess'' people have been asking for finding not only the best, but the $k$ best solutions. Sometimes it becomes a problem when these $k$ best solutions are too similar. This similarity problem may be overcome by demanding that the $k$ solutions obey certain distance conditions. We investigate the simplest case $k=2$ and we look at valuated matroids. We present several exemplary results, concerning also time complexity. These results are interesting in themselves. But they are also good references for similar studies in other fields with less smooth structures.}} @techreport{AltWen-TR-97, title = {{Two-best solutions under distance constraints: the model and exemplary results for matroids}}, author = {Ingo Alth{\"o}fer and Walter Wenzel}, institution = {Friedrich-Schiller-Universit{\"a}t Jena, Fakult{\"a}t f{\"u}r Mathematik und Informatik}, number = {Math/Inf/97/17}, month = {20 June}, year = {1997}, abstract = {In discrete maximization problems one typically wants to find an optimal solution. However, in topics like ``alignment of DNA-strings'', ``automatic speech recognition'', and ``computer chess'' people have been asking for finding not only the best, but the $k$ best solutions. Sometimes it becomes a problem when these $k$ best solutions are too similar. This similarity problem may be overcome by demanding that the $k$ solutions obey certain distance conditions. We investigate the simplest case $k=2$ and look at valuated matroids. We present several exemplary results, concerning also time complexity. These results are interesting in themselves. But they are also good references for similar studies in other fields with less smooth structures.}} @techreport{AltWen-TR-98, title = {{$k$-best solutions under distance constraints in valuated $\Delta$-matroids}}, author = {Ingo Alth{\"o}fer and Walter Wenzel}, institution = {Friedrich-Schiller-Universit{\"a}t Jena, Fakult{\"a}t f{\"u}r Mathematik und Informatik}, number = {Math/Inf/98/14}, month = {27 May}, year = {1998}, abstract = {In discrete maximization problems one usually wants to find an optimal solution. However, in several topics like ``alignments'', ``automatic speech recognition'', and ``computer chess'' people are interested to find the $k$ best solutions for some $k\ge 2$. We demand that the $k$ solutions obey certain distance constraints to avoid that the $k$ alternatives are too similar. Several results for valuated $\Delta$-matroids are presented, and we concern in particular time complexity.}} @inproceedings{AmiGha-IPEC-93, title = {{An expert system for transmission line route selection}}, author = {El-Amin and Al-Ghamdi}, booktitle = {Int. Power Engineering Conf}, publisher = {Nanyang Technol. Univ, Singapore}, volume = {2}, pages = {697--702}, year = {1993}, abstract = {An expert system (ES) is developed to help power system planners to choose the 'most suitable' transmission line route. The 'most suitable' route is the one that minimizes disruption to the surrounding environment as well as meeting any social constraints. The electric utility will tentatively identify up to five possible routes based on cost only. These routes are identified by the K-shortest path method. The chosen routes are then subjected to environmental and social factor using the developed ES. Factors such as crossing existing lines, running parallel to existing line, crossing crude oil pipelines etc. are considered. The ES assigns a cost value and weight for each factor and then normalizes the overall weight. The route with the lowest disruption is chosen. The ES was tested on a 69 kV distribution system for connecting two substations. The results obtained are in full agreement with the results obtained when complex integer goal programming (IGP) are used. They also conform with what the electric utility engineers expected.}} @techreport{AmTsuShi-TR-76, title = {{An algorithm for generating all the paths between two vertices in a digraph and its application}}, author = {T. D. Am and S. Tsukiyama and I. Shirakawa and H. Ozaki}, institution = {Osaka Univ.}, year = {1976}, abstract = {An algorithm to generate all the directed paths from a specified vertex to another one in a given directed graph is proposed. The algorithm requires the processing time bounded by the order $O((n+m)(p+1))$ and the memory space bounded by $O(n+m)$, where $n$, $m$, and $p$ denote the number of vertices, edges, and directed paths in a given directed graph, respectively. As an application of the algorithm, the shortest or the longest path problem in a directed graph containing cycles of negative weight is also considered.}} @inproceedings{AnaSchShu-ASSP-95, title = {{Duration modeling in large vocabulary speech recognition}}, author = {A. Anastasakos and Richard Schwartz and Han Shu}, booktitle = {Proc. Int. Conf. Acoustics, Speech, and Signal Processing}, publisher = {IEEE}, volume = {1}, pages = {628--631}, month = {May}, year = {1995}, abstract = {This paper presents a study of different methods for phoneme duration modeling in large vocabulary speech recognition. We investigate the employment of phoneme duration and the effect of context, speaking rate and lexical stress in the duration of phoneme segments in a large vocabulary speech recognition system. The duration models are used in a postprocessing phase of BYBLOS, our baseline HMM-based recognition system, to rescore the $N$-Best hypotheses. We describe experiments with the 5 K word ARPA Wall Street Journal (WSJ) corpus. The results show that integration of duration models that take into account context and speaking rate can improve the word accuracy of the baseline recognition system.}} @article{AniHas-SJC-89, title = {{Ranking the best binary trees}}, author = {S. Anily and Refael Hassin}, journal = {SIAM J. Computing}, publisher = {SIAM}, volume = {18}, pages = {882--892}, year = {1989}, review = {MR-91d-68098}} @article{MR-91d-68098, reviews = {AniHas-SJC-89}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Ranking the best binary trees}}, volume = {91d}, number = {68098}, year = {1991}, text = {The problem of ranking the $K$-best binary trees with respect to their weighted average leaves' levels is considered. Both the alphabetic case, where the order of the weights in the sequence $w\sb 1,\cdots,w\sb n$ must be preserved in the leaves of the tree, and the nonalphabetic case, where no such restriction is imposed, are studied. For the alphabetic case a simple algorithm is provided for ranking the $K$-best trees, based on a recursive formula of complexity $O(Kn\sp 3)$. For nonalphabetic trees two different ranking problems are considered, and for each of them it is shown that the next best tree can be solved by a dynamic programming formula of low complexity order.}} @inproceedings{ArdMal-ACCS-71, title = {{A recursive algorithm for generating circuits and related subgraphs}}, author = {M. T. Ardon and N. R. Malik}, booktitle = {Proc. 5th Asilomar Conf. Circuits {\&} Systems}, publisher = {Western Periodicals Co.}, editor = {S. R. Parker}, pages = {279--284}, year = {1972}, abstract = {A technique is proposed for efficiently finding the set of all or some specified sets of circuits, paths, directed circuits and directed paths of a directed graph. The method employs the matrix defined by $M=C+I$, where $C$ is the variable adjacency matrix of the graph, and $I$ is an identity matrix. The method is an extension of Lempel and Cederbaum's (1966) procedure. By their technique the directed circuits are found by applying the Boolean reduction to an expression which is resulted from the permanent expansion of $M$. Here, a new expansion, the pseudo-permanent, is defined by which the set of directed circuits is found directly. The procedure is then modified to obtain particular sets of directed circuits and an arbitrarily specified set of directed paths. An extension to nonoriented graphs results in an efficient algorithm for generating undirected circuits.}} @article{AriTsuShi-IEICE-79, title = {{Algorithms for enumerating all the $s$-$t$ cutsets in $O(|V|+|E|)$ per cutset}}, author = {H. Ariyoshi and S. Tsukiyama and I. Shirakawa and H. Ozaki}, journal = {IEICE Trans. Information {\&} Systems}, volume = {E62}, number = {1}, pages = {22--23}, month = {January}, year = {1979}, abstract = {Presents two algorithms with time complexity of $O((n+m)(\nu+1))$; one has space complexity of $O(n^2)$ and the other of $O(n+m)$, where $n$, $m$, and $\nu$ are the numbers of vertices, edges, and $s$-$t$ cutsets in a graph, respectively.}} @inproceedings{AsaSat-GTA-84, title = {{Long path enumeration algorithms for timing verification on large digital systems}}, author = {Tetsuo Asano and Shinichi Sato}, booktitle = {Graph Theory with Applications to Algorithms and Computer Science}, publisher = {Wiley-Interscience}, pages = {25--35}, year = {1984}, review = {MR-87b-94065}} @article{MR-87b-94065, reviews = {AsaSat-GTA-84}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Long path enumeration algorithms for timing verification on large digital systems}}, volume = {87b}, number = {94065}, year = {1987}, text = {To insure that a digital system will operate at a desired speed, the designer must verify that every path delay is not too long or too short. Thus, an efficient path enumeration technique is needed. In this paper we present two algorithms for enumerating all possible paths in a directed acyclic graph that exceed given delay time. They run in $O(m\log m+N(K))$ and $O(Km)$ time, respectively, and require $O(m+n)$ space, where $K,m$, and $n$ are the number of such long paths, arcs, and nodes of a graph, and $N(K)$ is the total number of nodes on $K$ such long paths.}} @article{Awa-IJPR-87, title = {{A counter-example to Naidu-Singh's myopic algorithm for generation of Wagner-Whitin optimal ordering plan (lot sizing)}}, author = {P. G. Awate}, journal = {Int. J. Production Res.}, volume = {25}, number = {8}, pages = {1235--1237}, month = {August}, year = {1987}, abstract = {The paper gives a simple counter-example to the conjecture by Naidu and Singh (see ibid., vol.24, no.1, p.223 (1986)) that their algorithm 'gives the optimal solution like the W-W algorithm'. Secondly, it points out that the Naidu-Singh procedure attempts to find the cheapest path in a certain acyclic network whose nodes are sets of periods and where the kth cheapest path does not necessarily have any node in common with 2nd or 3rd or. . .or (k-1)st-cheapest path.}} @article{AweBerCow-SJC-98, title = {{Near-linear time construction of sparse neighborhood covers}}, author = {Baruch Awerbuch and Bonnie Berger and Lenore Cowen and David Peleg}, journal = {SIAM J. Computing}, publisher = {SIAM}, volume = {28}, number = {1}, pages = {263--277}, year = {1998}, comment = {Despite the reference in the abstract to k-shortest-paths, what they actually approximate is the set of shortest paths for k source-destination pairs. Obviously this can be solved by k applications of Dijkstra in O(k(m+n log n)) time but they achieve a linear time approximation.}, abstract = {This paper introduces a near-linear time sequential algorithm for constructing a sparse neighborhood cover. This implies analogous improvements (from quadratic to near-linear time) for any problem whose solution relies on network decompositions, including small edge cuts in planar graphs, approximate shortest paths, and weight- and distance-preserving graph spanners. In particular, an O(log n) approximation to the k-shortest paths problem on an n-vertex, E-edge graph is obtained that runs in O(n+E+k) time.}} @article{AyaCab-DACS-92, title = {{Path enumeration and hot-potato routing analysis in multihop networks}}, author = {E. Ayanoglu and R. J. Caballero}, journal = {Int. J. Digital and Analog Communication Systems}, volume = {5}, pages = {217--223}, year = {1992}, abstract = {Using labelling of the edges of the network graph for a multihop network (using deflection routeing) and a Taylor series expansion of the transfer function of the resulting signal flow graph, the authors calculate the number of paths of a given length in the multihop network. The derivative of the transfer function and a fixed point algorithm yield the average delay as a function of the packet arrival rate.}} @article{AzeSanSil-EJOR-93, title = {{An algorithm for the ranking of shortest paths}}, author = {J. A. Azevedo and Santos Costa, M. E. O. and Silvestre Madeira, J. J. E. R. and Ernesto de Queir{\'o}s Vieira Martins}, journal = {Eur. J. Operational Research}, volume = {69}, pages = {97--106}, year = {1993}, abstract = {An efficient computational implementation of a path deletion $K$ shortest paths algorithm and a new algorithm for the same problem are presented. In a path deletion $K$ shortest paths algorithm a sequence $(G_1, G_2, \ldots, G_k)$ of networks is defined, such that $G_1$ is the given network and its $k$-th shortest path is trivially determined from the shortest path in $G_k$. In essence, as soon as the shortest path in $G_k$ is determined it is excluded from $G_k$ in such a way that no new paths are formed and no more paths are deleted. So, for each $G_k$, two procedures are executed: a shortest path algorithm and a path deletion algorithm. In the presented computational implementation, all the information resulting from the determination of the $k$-th shortest path is carried throughout $G_k+1, G_k+2, \ldots, G_k$. The new algorithm not only keeps this characteristic but also avoids the last $K-1$ executions of a shortest path algorithm, which results in a surprising and very substantial reduction in the execution time. In fact, for randomly generated networks with $10^4$ nodes and $10^5$ arcs, once the shortest path is determined, the new algorithm computes the next $100$ shortest paths in times of the order of $10^{-1}$ seconds. To illustrate the efficiency of this algorithm, comparative computational experiments are reported.}} @inproceedings{AzeSilMar-AIRO-90, title = {{A shortest paths ranking algorithm}}, author = {J. A. Azevedo and Silvestre Madeira, J. J. E. R. and Ernesto de Queir{\'o}s Vieira Martins and F. M. A. Pires}, booktitle = {Proc. AIRO 1990}, publisher = {Associazione Italiana Ricerca Operativa}, pages = {1001--1011}, year = {1990}, url = {http://www.mat.uc.pt/~eqvm/cientificos/investigacao/r_papers.html}, abstract = {The ranking of K shortest paths is a classical network optimization problem with a large range of real world applications. Take as an example the constrained shortest path problem, where some complex set of constraints is associated with each path. If these constraints are ignored and paths are listed by increasing order of objective values, the shortest path verifying the given set of constraints is thus determined. The shortest path ranking problem may also occur in the multiobjective shortest path problem. In fact, a procedure for determining the multiobjective shortest path involves the knowledge of a well defined set of paths, namely the set of nondominated paths, which can be computed by a shortest paths ranking algorithm. For the ranking of shortest paths (loopless or not) problem, there are three classes of algorithms. One of them is based on the {\it Principle of Optimality}, being Dreyfus' algorithm its most representative one. Another classe comprises the generalizations, due to Shier, of labeling shortest paths algorithms. Finally, the last class encompasses the algorithms based on the path deletion concept, due to one of the authors. A new algorithm belonging to this class is presented. We prove that, in a worst case analysis, its executation time is as good as that of Dreyfus' algorithm that, as far as we know, has been considered the best algorithm for the problem. Computational experiments showing its clearly better performance are also presented. As an example, we report tests on random networks with 1500 nodes and 15000 arcs where the new algorithm to determine 250 paths was about 60 times faster than Dreyfus' algorithm.}} @article{AzeSilMar-EJOR-94, title = {{A computational improvement for a shortest paths ranking algorithm}}, author = {J. A. Azevedo and Silvestre Madeira, J. J. E. R. and Ernesto de Queir{\'o}s Vieira Martins and F. M. A. Pires}, journal = {Eur. J. Operational Research}, volume = {73}, pages = {188--191}, year = {1994}, abstract = {Presents a computational improvement for the shortest paths ranking algorithm due to some of the authors. According to its computational complexity, this new version of the algorithm entails a very significant reduction in its execution time and an even larger reduction in the required computer memory space. Computational experiments are reported.}} @article{AziSobSam-MR-94, title = {{Fast enumeration of every path in a reliability graph using subgraphs}}, author = {M. A. Aziz and M. A. Sobhan and M. A. Samad}, journal = {Microelectronics and Reliability}, volume = {34}, pages = {1395--1396}, year = {1994}, abstract = {A fast method has been proposed for enumeration of all possible pathsets from every node to all other nodes using subgraphs. The method efficiently identifies the elements as well as source, sink and other nodes constituting a path. It performs no multiplications other than a few additions of binary digits.}} @article{BaaAshAnw-Tr-96, title = {{Transportation analysis for sludge landfill site selection -- a case study demonstration}}, author = {M. H. Baaj and S. Ashur and A. Anwar}, journal = {Transportation}, volume = {23}, number = {2}, pages = {191--209}, month = {May}, year = {1996}, note = {A solution framework for the Sludge Landfill Site Selection Problem (SLSSP) which arises in the context of environmental planning is presented. The problem may be defined as follows: given a set of environmentally acceptable candidate landfill sites, identify the site which minimizes a weighted combination of two objectives (system descriptors): the present worth value of the transportation operation costs and the resulting population disturbance of the chosen set of transportation routes. The solution framework relies on an analysis algorithm which identifies K shortest travel time routes between one candidate landfill site and each of the water treatment plants. Based on a prespecified tradeoff between present worth and population disturbance, the transportation routes associated with each landfill site are selected and the site's two resulting system descriptors are computed. The solution methodology is demonstrated on data developed for the City of Phoenix, Arizona. In addition, computational experiments are performed to rest the quality of solution and its sensitivity to different tradeoffs between the two system descriptors. As a result of this study, city officials were dissuaded away from a prefavored landfill site. Final selection from the set of pareto-optimal solutions was postponed pending results of ongoing efforts to enlarge the collection operation by including sludge disposed in other neighboring cities.}} @article{BabFunNis-IEICE-98, title = {{A proposal of a greedy neural network for route assignments in multihop radio networks}}, author = {T. Baba and N. Funabiki and S. Nishikawa}, journal = {Trans. IEICE}, volume = {J81D-I}, number = {6}, pages = {700--707}, month = {June}, year = {1998}, abstract = {In a multihop radio network, packets are transmitted from source nodes to destination nodes by activating several links between nodes. Each node can either send a packet to, or receive a packet from, almost one of its adjacent nodes simultaneously. In order to minimize the transmission time for given requests, the route assignment problem must be solved to assign a transmission route for each request, and the link activation problem must be solved to find a link activation schedule. The route assignment problem is decomposed into two sub-problems: the candidate extraction problem and the route selection problem. We propose a cost function for the route assignment problem and secondly, we propose the k-shortest route extraction method for the candidate extraction problem. This method is based on the k-shortest path algorithm, and extracts only routes whose number of hops is limited by the largest length among the shortest routes for all the SD pairs without loops and redundant nodes. The number of different extracted candidates is also limited by the minimum number of hops for each request. Thirdly, we propose the greedy neural network algorithm for the route selection problem. The greedy neural network consists of the greedy initialization method with the number of hops of the corresponding candidate, the motion equation with the w function and the new term of minimizing the cost function, and the one dimensional maximum neutron model. Through simulations in up to 500-node networks, we verify that our algorithm finds better solutions in shorter time with smaller space than the existing algorithms.}} @article{BabFunNis-SCJ-99, title = {{A proposal of a greedy neural network for route assignments in multihop radio networks}}, author = {T. Baba and N. Funabiki and S. Nishikawa}, journal = {Systems and Computers in Japan}, volume = {30}, number = {13}, pages = {52--60}, month = {November}, year = {1999}} @article{Bak-MOS-76, title = {{All paths in an activity network}}, author = {A. Bako}, journal = {Mathematische Operationsforschung und Statistik}, volume = {7}, pages = {851--858}, year = {1976}, abstract = {The known CPM/PERT methods are available for the determination of the critical edges and a critical path. This paper gives two algorithms: one of them is used for the determination of all critical paths, the second for the determination of the second longest paths. The validity of the algorithms and the labelling technique are also given.}} @article{BakKas-Sz-77, title = {{Determining the $k$-th shortest path by matrix method}}, author = {A. Bako and P. Kas}, journal = {Szigma}, volume = {10}, pages = {61--66}, year = {1977}, abstract = {An algorithm is given for the multiterminal version of the $k$-th shortest path problem. The algorithm calculates in n steps the length of the first $k$ paths between all the point pairs of a digraph. The labelling technique required for the determination of the paths and the procedure supplying the intermediate points belonging to the path are described. Altogether the calculation consists of $kn^3$ additions and $k^3/2 n^3$ [Note - this formula was garbled, I have attempted to reconstruct it but may have erred - DE] comparisons. This number is considerably lower than what is necessary for the repeated application of the $k$-th shortest path algorithm of two end points known in literature.}, note = {In Hungarian}} @phdthesis{Bal-PhD-87, title = {{A Network Model for Rotating Workforce Scheduling and Related Problems}}, author = {Nagraj Balakrishnan}, school = {Purdue Univ., Dept. of Business Administration}, year = {1987}, abstract = {The rotating workforce scheduling problem, which is an important factor in improving worker productivity, involves the construction of an efficient sequence of work and recreation periods spanning over a number of weeks. This schedule must satisfy the workforce requirements during the various time periods and conform to all the other conditions imposed on the work/recreation periods and their sequence. We consider the modelling of the rotating workforce scheduling problem as a network flow problem. All the conditions enforced on the problem are incorporated in the network itself, except for the staff-covering constraints which are treated as side constraints. The optimal solution to the problem is a path in the network and is identified using a dual-based approach. The model deals with the three issues of recreation period identification, work/recreation period sequencing and shift scheduling simultaneously, and is designed to handle multiple shifts with time varying demands. A software package which includes the network model along with the solution technique is developed. To illustrate its use, the procedure, which is capable of solving large-scale problems, is applied to three well-known problems in rotating workforce scheduling. The computational results presented indicate that this procedure provides us with a useful method of solving large-scale complex problems in workforce scheduling. The general model developed can also be applied to other problems in sequencing and scheduling. To illustrate this feature, we consider a particular aspect of the examination timetabling problem where the objective is to assign blocks of examinations to time periods such that the number of students having back-to-back conflicts is minimized. The time periods are defined in such a way that the last period of any day and the first period of the following day are not considered to be back-to-back. The problem is modelled as a network flow problem where the solution to the problem is the shortest path in the network subject to side-constraints. A dual based approach followed by a K-shortest path enumeration technique is employed to identify this optimal path. The procedure is tested on a variety of test problems including a real problem faced by a large university.}} @article{BalDerHil-Nw-90, title = {{Matching problems with generalized upper bound side constraints}}, author = {Michael O. Ball and Ulrich Derigs and C. Hilbrand and Achim Metz}, journal = {Networks}, volume = {20}, number = {6}, pages = {703--721}, year = {1990}, review = {MR-91h-90068}} @article{MR-91h-90068, reviews = {BalDerHil-Nw-90}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Matching problems with generalized upper bound side constraints}}, author = {Frank Werner}, volume = {91h}, number = {90068}, year = {1991}, text = {The paper considers procedures for the approximate solution of matching problems with generalized upper bound side constraints which are based on Lagrangian relaxation and dual ascent. In the first phase the standard Langrangian relaxation ideas are used to determine lower bounds for matching problems with side constraints. In the second phase an improvement technique is applied to the subsequences of feasible and infeasible matchings obtained in phase one. Namely, a knapsack heuristic is applied to any pair of feasible/infeasible matchings to construct better feasible matchings. If the optimal solution is desired, then an enumeration phase, in which a sequence of $k$-best matchings with respect to a penalized objective function is constructed, can be added. Finally, computational results are presented for a set of test problems with one and five constraints.}} @inproceedings{BalSte-AFCT-91, title = {{Topologies for linear lightwave networks}}, author = {K. Bala and T. E. Stern}, booktitle = {Advanced Fiber Communications Technologies}, number = {1579}, series = {Proc. SPIE}, publisher = {Int. Soc. Optical Engineering}, pages = {62--73}, year = {1991}, abstract = {Tree based networks which preclude the possibility of certain violations are compared with networks that allow violations but achieve better load distribution. The performance of each topology, from the point of view of blocking probability is compared by a simulator using call routing based on the $K$-shortest path algorithm. It is found that general topologies that allow for better load distribution perform better than tree based topologies.}} @inproceedings{BalSteBal-INFOCOM-91, title = {{Algorithms for routing in a linear lightwave network}}, author = {K. Bala and T. E. Stern and K. Bala}, booktitle = {Proc. 10th Joint. Conf. IEEE Computer {\&} Communications Socs.}, volume = {1}, pages = {1--9}, year = {1991}, abstract = {Routing algorithms are proposed for setting up calls on a circuit-switched basis in linear lightwave networks (LLN), i.e., networks composed only of linear components, including controllable power combiners and dividers, and possibly linear (non-regenerative) optical amplifiers. The overall problem is decomposed into three subproblems: (1) physical path allocation, (2) checking for violations of the special optical constraints on the allocated physical path, and (3) channel assignment. Only point to point connections are considered. The physical path allocation technique uses the K-shortest path algorithm and tries to minimize the number of sources potentially interfering with each other, as a result of the incoming call. A channel assignment heuristic that tends to spread out calls evenly among the available channels works better than one that tries to maximize channel reuse.}} @article{BalSteSim-TN-95, title = {{Routing in a linear lightwave network}}, author = {K. Bala and T. E. Stern and D. Simchi-Levi and K. Bala}, journal = {Trans. on Networking}, publisher = {IEEE and ACM}, volume = {3}, number = {4}, pages = {459--469}, month = {August}, year = {1995}, abstract = {Dynamic routing of point-to-point connections in a waveband selective linear lightwave network is addressed. Linear lightwave networks are all optical networks in which only linear operations are performed on signals in a waveband selective manner. Special constraints arise because of the linearity in the linear lightwave network. The overall problem of finding a path satisfying all the routing constraints for point-to-point connections is shown to be very complex. Owing to the complexity, the overall routing problem is decomposed into several subproblems. In particular, given a request for a point-to-point connection a waveband is first chosen for the call. Two heuristics, MAXBAND which allocates the most used band to a call and another MINBAND (least used band) are studied. Then, the problem of routing in a given waveband is further divided into smaller subproblems of finding a path in the waveband, checking for feasibility of the path in the chosen waveband and channel allocation (within the waveband). For finding paths in a waveband, K-SP, BLOW-UP and MIN-INT algorithms are proposed. A recursive algorithm checks for feasibility of the path on the waveband. Two channel allocation schemes (within a single waveband) MIN and MAX are presented. Simulations show that using MAXBAND (waveband), MIN-INT (path on waveband) and MIN (channel within waveband) policies resulted in the best performance (least blocking).}} @phdthesis{Bar-PhD-95, title = {{A Quasi-Static Routing Optimization Model for Telecommunication Networks}}, author = {Michael Raymond Bartolacci}, school = {LeHigh Univ., Dept. of Industrial Engineering}, year = {1995}, abstract = {The main focus of this research is the development of a routing optimization model for telecommunication networks that utilizes nodal clustering as a 'preprocessor' to routing. The routing model developed contains three submodels: the clustering submodel (CLUS), the inter-cluster routing submodel (INTER), and the intra-cluster routing submodel (INTRA). The clustering problem is solved through a modified version of 'problem space' search, while inter-cluster and intra-cluster routing is conducted in a dynamic manner. This clustered routing method out-performed a standard dynamic routing algorithm and a static approach with respect to minimizing average source-to-destination routing delay. A secondary focus of this research is the generation of test problem sets for telecommunication network routing. A procedure is developed which generates topologies with random geometric structures. A set of test problems based on PREPNET, a mid-level network on the NSFnet backbone, are also developed. A third focus of this research is a static, k shortest path-based, approach for bifurcated and single path routing in telecommunication networks. This proposed routing method is tested against a single path routing algorithm for a variety of network topologies and traffic requirements.}} @techreport{BarKhuSch-TR-95, title = {{The complexity of finding most vital arcs and nodes}}, author = {Amotz Bar-Noy and Samir Khuller and Baruch Schieber}, organization = {Univ. of Maryland, Dept. of Computer Science}, number = {CS-TR-3539}, month = {November}, year = {1995}, url = {ftp://ftp.cs.umd.edu/pub/papers/papers/3539/3539.ps.Z}, abstract = {Let $G(V,E)$ be a graph (either directed or undirected) with a non-negative length $\ell(e)$ associated with each arc e in E. For two specified nodes s and t in V, the k most vital arcs (or nodes) are those k arcs (nodes) whose removal maximizes the increase in the length of the shortest path from s to t. We prove that finding the k most vital arcs (or nodes) is NP-hard, even when all arcs have unit length. We also correct some errors in an earlier paper by Malik, Mittal and Gupta \cite{MalMitGup-ORL-89}.}} @article{BarZie-SMC-91, title = {{Topological analysis of satellite-based distributed sensor networks}}, author = {Craig M. Barnhart and R. E. Ziemer}, journal = {Trans. Systems, Man, and Cybernetics}, publisher = {IEEE}, volume = {21}, number = {5}, pages = {1060--1070}, year = {1991}, abstract = {A method for evaluating the topological quality of networks for distributed sensor applications is presented. The criteria for evaluation are network survivability and delay. Nodal connectivity is used to characterize survivability, and mean path length is used to characterize delay. To calculate these two quantities, an algorithm is developed to find k shortest node-disjoint paths between a pair of nodes when each link has unit distance. As an example of the use of this type of analysis, the effects of nodal losses in a multiple-node satellite network consisting of a Walker low-orbit sphere and a geosynchronous constellation are examined. The example demonstrates how topological analysis on the basis of connectivity and mean path length may be used to detect, and subsequently address, potential flaws in a network design. The results show that the geosynchronous/low-orbit link assignment protocol should be a primary concern in the design of this network. They also show that the nodal degree of the failed node, and the distribution of links between the Walker sphere and the geosynchronous constellation, are the fundamental determinants of mean path length.}} @article{Bax-IPL-94, title = {{Algorithms to count paths and cycles}}, author = {Eric Theodore Bax}, journal = {Information Processing Letters}, volume = {52}, number = {5}, pages = {249--252}, month = {December}, year = {1994}, abstract = {We use results for Hamiltonian cycles and paths to deduce $O(2^n{\rm poly}(n))$ time and $O({\rm poly}(n))$ space algorithms to count: (1) cycles on a single vertex, (2) all cycles, (3) paths between a given pair of vertices, and (4) all paths in a graph with $n$ vertices.}, review = {MR-95h-68072}} @article{MR-95h-68072, reviews = {Bax-IPL-94}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Algorithms to count paths and cycles}}, volume = {95h}, number = {68072}, year = {1995}} @phdthesis{Bax-PhD-98, title = {{Finite-Difference Algorithms for Counting Problems}}, author = {Eric Theodore Bax}, school = {California Inst. of Technology, Dept. of Computer Science}, year = {1998}, abstract = {We present a novel method to construct counting algorithms: (1) Construct a generating function in which one type of terms corresponds to the objects to be counted. (2) Apply the proper finite-difference operators to produce a formula that counts the terms. (3) Choose finite-difference parameters to reduce the computation required to evaluate the formula. We compare this finite-difference method to two other methods, the dynamic programming method and the inclusion and exclusion method. Using the problem of counting Hamiltonian paths as an example, we show that finite-difference algorithms require only polynomial space for problems for which dynamic programming algorithms require exponential space. Also, we show that finite-difference algorithms are a generalization of inclusion and exclusion algorithms. Finite-difference algorithms have some free parameters, and inclusion and exclusion algorithms correspond to a particular setting of those parameters. Using the 0-1 matrix permanent problem as an example, we show that the finite-difference parameters can be chosen to produce finite-difference algorithms that are faster than their inclusion and exclusion counterparts. We use the problems of counting paths by length and counting independent path sets to illustrate how the flexibility of generating functions and extensions to finite-difference operators allow the development of finite-difference algorithms for problems beyond the realm of inclusion and exclusion. Furthermore, we use the problems of sequencing, bin packing, and deadlock avoidance to demonstrate the development of finite-difference algorithms for NP-complete and {\#}P-complete problems.}} @article{Bei-Comp-72, title = {{An algorithm for finding all $k$-shortest distances in a network}}, author = {H. Beilner}, journal = {Computing}, volume = {10}, pages = {205--220}, year = {1972}, abstract = {This paper describes a new matrix-algorithm for determining all shortest up to $k$-shortest distances between the $n$ vertices of a network. The outstanding property of this algorithm consists in the necessary amount of additions/subtractions which can be estimated, for $n\gg k$, not to exceed $1/3 n^5/2 k^5/2 + 5 n^5/2 k^3/2 + O(n^3/2 k^5/2)$ whereas the number of comparisons lies, as in other algorithms, in the range of $n^3 k^3$. This paper also includes a formal proof of the validity of the algorithm and a short comparison with different, known methods.}, note = {In German}} @article{Bel-QAM-58, title = {{On a routing problem}}, author = {Richard E. Bellman}, journal = {Quarterly of Applied Mathematics}, volume = {16}, number = {1}, pages = {87--90}, year = {1958}} @article{BelKal-SIAM-60, title = {{On $k$th best policies}}, author = {Richard E. Bellman and R. Kalaba}, journal = {J. SIAM}, publisher = {SIAM}, volume = {8}, pages = {582--588}, year = {1960}, review = {MR-22-13305}} @article{MR-22-13305, reviews = {BelKal-SIAM-60}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{On $k$th best policies}}, author = {T. E. Hull}, volume = {22}, number = {{\#}13305}, year = {1961}} @article{BerGenPot-JH-00, title = {{Tabu search for a network loading problem with multiple facilities}}, author = {D. Berger and B. Gendron and J.-Y. Potvin and S. Raghavan and P. Soriano}, journal = {J. Heuristics}, volume = {6}, number = {2}, pages = {253--267}, month = {June}, year = {2000}, abstract = {Examines a network design problem that arises in the telecommunications industry. In this problem, communication between a gateway vertex and a number of demand vertices is achieved through a network of fiber-optic cables. Since each cable has an associated capacity (bandwidth), enough capacity must be installed on the links of the network to satisfy the demand, possibly using different types of cables. Starting with a network with no capacity or some capacity already installed, a tabu search heuristic is designed to find a solution that minimizes the cost of installing any additional capacity on the network. This tabu search applies a k-shortest path algorithm to find alternative paths from the gateway to the demand vertices. Numerical results are presented on different types of networks with up to 200 vertices and 100 demand vertices.}} @inproceedings{BesKel-AWOCA-99, title = {{Algorithms for shortest paths and $d$-cycle problems}}, author = {Sergei Bespamyatnikh and Andrei Kelarev}, booktitle = {Proc. 10th Aust. Worksh. Combinatorial Algorithms}, pages = {152--156}, year = {1999}, url = {http://www.cs.ubc.ca/~besp/cycle.ps.gz}, abstract = {Let $G$ be a weighted graph with $n$ vertices and $m$ edges. We address the $d$-cycle problem, i.e., the problem of finding a subgraph of minimum weight with given cyclomatic number $d$. Hartvigsen [5] presented an algorithm with running time $O(n^2 m)$ and $O(n^{2d-1} m^2)$ for the cyclomatic numbers $d=1$ and $d\ge 2$, respectively. Using a $(d+1)$-shortest-paths algorithm, we develop a new more efficient algorithm for the $d$-cycle problem with running time $O(n^{2d-1} + n^2 m+ n^3\log n)$.}} @inproceedings{BetHil-ASSP-95, title = {{Language models for a spelled letter recognizer}}, author = {M. Betz and H. Hild}, booktitle = {Proc. Int. Conf. Acoustics, Speech, and Signal Processing}, publisher = {IEEE}, volume = {1}, pages = {856--859}, month = {May}, year = {1995}, abstract = {In some speech recognition applications, it is reasonable to constrain the search space of a speech recognizer to a large but finite set of sentences. We demonstrate the problem on a spelling task, where the recognition of continuously spelled last names is constrained to 110000 entries (=43000 unique names) of a telephone book. Several techniques to address this problem are compared: recognition without any language model, bigrams, functions to map a hypothesis onto a legal string, $n$-best lists, and finally a newly developed method which integrates all constraints directly into the search process within reasonable memory and time bounds. The baseline result of 56{\%} string accuracy is improved to 62, 85, 88, and 92{\%}, respectively.}} @article{BilEll-JPDC-95, title = {{An algorithm for finding the $K$-best allocations of a tree structured program}}, author = {A. Billionnet and S. Elloumi}, journal = {J. Parallel and Distributed Computing}, volume = {26}, pages = {225--232}, year = {1995}, abstract = {We consider the problem of allocating $n$ tasks of a distributed program to $m$ processors of a distributed system in order to minimize total communication and processing costs. If the intertask communication can be represented by a tree and if the communication costs are uniform, it is known that an optimal allocation can be determined in $O(nm)$ time. A $K$-optimal solution set $\Omega=(A_1,\ldots,A_K)$ of a given task allocation problem is a set of allocations such that no allocation $A$ which is not contained in $\Omega$ is better than any $A_i$, $i=1,\ldots,K$. In this paper, an algorithm is presented which computes a $K$-optimal set for the considered task allocation problem in $O(Knm)$.}} @article{Bof-RAIRO-93, title = {{The all-to-all alternative route problem}}, author = {Brian Boffey}, journal = {Revue Francaise d'Automatique Informatique Recherche Operationelle (RAIRO)}, volume = {27}, pages = {375--387}, year = {1993}, review = {MR-94h-90061}} @article{MR-94h-90061, reviews = {Bof-RAIRO-93}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{The all-to-all alternative route problem}}, volume = {94h}, number = {90061}, year = {1994}, text = {There are various $K$-best route problems associated with a network. The one studied here is that of finding, for all node pairs $(s,t)$, a best route from $s$ to $t$ together with an alternative route which is optimal subject to not containing the first edge of the best route. The relevance of this problem to dynamic vehicle guidance and to routing in communication networks is briefly discussed. An algorithm is developed whose complexity, under conditions likely to be met in practice, is established. An illustrative example is given.}} @article{BooWes-Algo-94, title = {{A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs}}, author = {Heather Booth and Jeffery Westbrook}, journal = {Algorithmica}, volume = {11}, number = {4}, pages = {341--352}, month = {April}, year = {1994}, abstract = {We give a linear time and space algorithm for analyzing trees in planar graphs. The algorithm can be used to analyze the sensitivity of a minimum spanning tree to changes in edge costs, to find its replacement edges, and to verify its minimality. It can also be used to analyze the sensitivity of a single-source shortest-path tree to changes in edge costs, and to analyze the sensitivity of a minimum-cost network flow. The algorithm is simple and practical. It uses the properties of a planar embedding, combined with a heap-ordered queue data structure.}} @inproceedings{BraSin-PEW-95, title = {{A comparative study of $k$-shortest path algorithms}}, author = {A. W. Brander and Mark C. Sinclair}, booktitle = {Proc. 11th UK Performance Engineering Worksh. for Computer and Telecommunications Systems}, month = {September}, year = {1995}, url = {http://esewww.essex.ac.uk/~mcs/ps/ukpew11_bra.ps.gz}, abstract = {Efficient management of networks requires that the shortest route from one point (node) to another is known; this is termed the shortest path. It is often necessary to be able to determine alternative routes through the network, in case any part of the shortest path is damaged or busy. The k-shortest paths represent an ordered list of the alternative routes available. Four algorithms were selected for more detailed study from over seventy papers written on this subject since the 1950s. These four were implemented in the `C' programming language and, on the basis of the results, an assessment was made of their relative performance.}} @techreport{Bro-RR-126, title = {{The 1993 SRC Algorithm Animation Festival}}, author = {Marc H. Brown}, type = {SRC Research Report}, institution = {Digital Equipment Corp.}, number = {126}, month = {29 July}, year = {1994}, url = {http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-126.html}} @article{BruGhiImp-EJOR-98, title = {{A multi-modal approach to the location of a rapid transit line}}, author = {G. Bruno and G. Ghiani and G. Improta}, journal = {Eur. J. Operational Research}, volume = {104}, number = {2}, pages = {321--332}, month = {January}, year = {1998}, abstract = {The location of a rapid transit line (RTL) represents a very complex decision problem because of the large number of decision makers, unquantifiable criteria and uncertain data. In this context operational research can help in the design process by providing tools to generate and assess alternative solutions. For this purpose two bicriterion mathematical programming models-the maximum coverage shortest path model and the median shortest path model-have been developed in the past. In this paper a new bicriterion model, which can evaluate in a more realistic way the attractivity of an RTL is introduced. To calculate an estimation of the non-inferior solution set of the problem, a procedure based on a k-shortest path algorithm was developed. This approach was applied to a well-known sample problem and the results are discussed and compared with those obtained using a median shortest path model.}} @inproceedings{BruGhiImp-ESI-95, title = {{A multi-modal approach to the location of a rapid transit line}}, author = {G. Bruno and G. Ghiani and G. Improta}, journal = {Proc. 12th EURO Summer Inst. Locational Analysis}, month = {June}, year = {1995}} @inproceedings{BruGhiImp-IFORS-97, title = {{Models and algorithms for the design of rapid transit networks}}, author = {G. Bruno and G. Ghiani and G. Improta}, booktitle = {Proc. 7th Int. Special Conf. IFORS, Information Systems in Logistics and Transportation}, month = {June}, year = {1997}, abstract = {Traditional underground metro systems, rapid rail transit systems are becoming more and more common to improve mobility in large urban areas. The design of such systems is a very critical task which has long term effects on modal aplit. Decisions are to be made about topological configuration, the number and location of lines and stations, line frequencies etc.. In this context decision making is a complex job as several players are involved, some objectives are unquantifiable and estimation of the non-inferior solutions set considering the two main quantifiable objectives (e.g. the construction cost and a measure of the social benefit); second, the choice, among the previously selected solutions, of the most suitable configuration by means of the remaining objectives. In the present paper we tackle the first step generalising a k-shortest path technique in such a way to consider complex topological patterns (grids, stars, cartwheels, triangles etc.). The proposed method was used to simulate the Rome metro system.}} @article{BruHam-EJOR-89, title = {{$K$-optimal solution sets for some polynomially solvable scheduling problems}}, author = {Peter Brucker and Horst W. Hamacher}, journal = {Eur. J. Operational Research}, volume = {41}, number = {2}, pages = {194--202}, year = {1989}, review = {MR-90e-90069}} @article{MR-90e-90069, reviews = {BruHam-EJOR-89}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{$K$-optimal solution sets for some polynomially solvable scheduling problems}}, volume = {90e}, number = {90069}, year = {1990}, text = {A $k$-optimal solution set $\Omega=\{S\sb 1,\cdots,S\sb k\}$ of a given scheduling problem is a set of schedules such that no schedule $S$ which is not contained in $\Omega$ is better than any $S\sb i$, $i=1, \cdots,k$. $k$-optimal sets are useful in offering alternatives to a single optimal schedule. In this paper algorithms are presented which compute $k$-optimal sets for various scheduling problems for which the optimal schedule can be computed in polynomial time.}} @inproceedings{BurHaf-SEC-74, title = {{A ranking problem on graphs}}, author = {R. N. Burns and Charles Edward Haff}, booktitle = {Proc. 5th Southeast Conf. Combinatorics, Graph Theory {\&} Computing}, number = {11}, series = {Graph Theory and Computing}, publisher = {Utilitas Mathematica Publishing}, address = {Winnepeg, Canada}, pages = {461--470}, year = {1974}} @inproceedings{BusLocOls-GC-94, title = {{Dynamic $K$-shortest path (DKSP) facility restoration algorithm}}, author = {M. T. Busche and C. M. Lockhart and C. Olszewski}, booktitle = {GLOBECOM, Communications: The Global Bridge}, publisher = {IEEE}, volume = {1}, pages = {536--542}, year = {1994}, abstract = {This paper describes the dynamic $K$-shortest path (DKSP) algorithm for distributed facility restoration and its performance in a simulation of AT{\&}T's high-capacity digital facilities network. The guiding paradigm of this algorithm is that of a switched network. At each facility node in the network, a local controller (LC) directs the activities of a digital cross-connect system (DCS) to route high-capacity digital connections around failures. The LCs communicate with each other via a connectionless network using routers and signaling links embedded in the transmission systems between nodes. After a failure, the LCs disseminate information about failed transmission links to the whole network. High-capacity digital connections are then restored by a call-control protocol. The simulation shows that the algorithm's efficiency is close to that of a centralized algorithm, and that its rate of finding alternate routes in this large network is approximately 50 ms per restoration path.}} @phdthesis{Bye-PhD-82, title = {{Optimal and Near-Optimal Policies for Discrete Deterministic Dynamic Programming Models}}, author = {Thomas Hancock Byers}, school = {Univ. of California, Berkeley, Dept. of Economics}, year = {1982}, abstract = {A new algorithm for finding policies with objective function values in a neighborhood of the optimum for certain dynamic programming models is presented and compared to the best available algorithms. The algorithm combines the 'depth-first' search with 'stacking' techniques of theoretical computer science and principles from dynamic programming to modify the usual backtracking routine and list all near-optimal policies. This is the first practical algorithm for a variety of large problems that are of interest. Two such problems are critical path analysis in project management and sequence alignment in molecular biology.}} @article{ByeWat-OR-84, title = {{Determining all optimal and near-optimal solutions when solving shortest path problems by dynamic programming}}, author = {Thomas Hancock Byers and Michael S. Waterman}, journal = {Operations Research}, volume = {32}, pages = {1381--1384}, year = {1984}, abstract = {Presents a new algorithm for finding all solutions with objective function values in the neighborhood of the optimum for certain dynamic programming models, including shortest path problems. The new algorithm combines the depth-first search with stacking techniques of theoretical computer science and principles from dynamic programming to modify the usual backtracking routine and lists all near-optimal policies. The resulting procedure is the first practical algorithm for a variety of large problems that are of interest.}} @techreport{CamFraMaf-LCE-73, title = {{The $k$ shortest spanning trees of a graph}}, author = {P. M. Camerini and L. Fratta and F. Maffioli}, institution = {IEEE-LCE Politechnico di Milano, Italy}, number = {73-10}, year = {1973}} @article{CamFraMaf-Nw-80, title = {{The $k$ best spanning arborescences of a network}}, author = {P. M. Camerini and L. Fratta and F. Maffioli}, journal = {Networks}, volume = {10}, number = {2}, pages = {91--110}, year = {1980}, review = {MR-81h-68023}} @article{MR-81h-68023, reviews = {CamFraMaf-Nw-80}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{The $k$ best spanning arborescences of a network}}, author = {Lawrence V. Saxton}, volume = {81h}, number = {68023}, year = {1981}, text = {The authors exhibit an efficient algorithm (in terms of both time and space) for finding the $K$ best spanning arborescences (i.e. a branching with a unique root) of a network. The algorithm given for the best arborescence is an adaptation of Tarjan's algorithm for finding the optimum branching of a network. To this is added a procedure for finding the next best spanning arborescence. The result is an algorithm for finding the $K$ best spanning arborescences of a network of $n$ vertices and $m$ edges in time $O(Km\log n)$ and space $O(K+m)$. They also note that, for dense networks, the algorithm can be modified to operate in time $O(n^2)$.}} @article{CarLiLut-DAM-97, title = {{Reliability evaluation of large telecommunication networks}}, author = {Jacques Carlier and Yu Li and Jean-Luc Lutton}, journal = {Discrete Applied Mathematics}, volume = {76}, pages = {61--80}, month = {June}, year = {1997}, abstract = {In this paper, we describe an approximation method to evaluate the reliability of large telecommunication networks based on optic fibre and digital cross-connect systems (DCS). The reliability measures are defined as the availability and the expected lost traffic. Their evaluation is decomposed into the rerouting calculation and the probabilistic calculation. The rerouting calculation (restoration from failures) is accomplished by a heuristic method using the $K$-shortest paths. It is made very rapidly, thanks to a sophisticated data structure. The probabilistic calculation is based on the stratified sampling which results in computational savings of several orders of magnitude and is well suited to very large networks with high reliability components.}, review = {MR-98c-90035}} @article{MR-98c-90035, reviews = {CarLiLut-DAM-97}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Reliability evaluation of large telecommunication networks}}, volume = {98c}, number = {90035}, year = {1998}} @inproceedings{CarSod-SOR-83, title = {{A binary enumeration tree to find $K$ shortest paths}}, author = {Paulo Carraresi and Claudio Sodini}, booktitle = {Proc. 7th Symp. Operations Research}, number = {45}, series = {Methods of Operations Research}, publisher = {Athen{\"a}um/Hain/Hanstein}, pages = {177--188}, year = {1983}, review = {MR-85i-90053}} @article{MR-85i-90053, reviews = {CarSod-SOR-83}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{A binary enumeration tree to find $K$ shortest paths}}, volume = {85i}, number = {90053}, year = {1985}, text = {The $K$ shortest simple paths problem in a directed graph is considered. A procedure based on a binary enumeration tree yields the solution by computing $K-1$ `second shortest paths' in appropriate graphs. The latter problems are shown to be related to the determination of the best basis adjacent to the optimal one in a minimum cost network flow problem, for which a dual approach is proposed.}} @inproceedings{CasRusVit-STS-97, title = {{Stochastic user equilibrium assignment with explicit path enumeration: comparison of models and algorithms}}, author = {E. Cascetta and Francesco Russo and Antonino Vitetta}, booktitle = {Proc. 8th Int. Symp. Transportation Systems}, year = {1997}, abstract = {In this paper a preliminary analysis of alternative models for ``feasible'' path generation and choice is presented. In particular a k-shortest path multi-criteria model for path enumeration is explored and different choice models (Logit, recently proposed C-Logit and Probit) are tested by comparing SUE assignment link flows with counts on an urban road network. Flows are also compared for more traditional DUE and SUE Probit implicit path enumeration models. The results obtained show that a limited number (4-7) of paths generated with rather ``simple'' criteria give satisfactory results, SUE with explicit path enumeration is largely comparible with, and in some cases superior to, traditional implicit SUE and DUE models. Explicit path enumeration allow also the specification of more sophisticated non additive attributes in the utility function of route choice models. From the computational point of view the explicit path C-Logit and Probit SUE algorithms are from three to twenty times superior to the implicit Probit SUE assignment.}} @inproceedings{Cha-CPM-94, title = {{Computing all suboptimal alignments in linear space}}, author = {Kun-Mao Chao}, booktitle = {Proc. 5th Symp. Combinatorial Pattern Matching}, number = {807}, series = {Lecture Notes in Computer Science}, publisher = {Springer Verlag}, pages = {31--42}, year = {1994}} @article{Cha-CT-68, title = {{Generation of trees, two-trees, and storage of master forests}}, author = {J. P. Char}, journal = {Trans. Circuit Theory}, publisher = {IEEE}, volume = {CT-15}, pages = {228--238}, year = {1968}, review = {MR-39-6779}} @article{MR-39-6779, reviews = {Cha-CT-68}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Generation of trees, two-trees, and storage of master forests}}, volume = {39}, number = {6779}, year = {1970}} @article{Cha-IS-98, title = {{On computing all suboptimal alignments}}, author = {Kun-Mao Chao}, journal = {Information Sciences}, volume = {105}, number = {1--4}, pages = {189--207}, month = {March}, year = {1998}, abstract = {Naor and Brutlag [D. Naor, D. Brutlag, Proceedings of the Fourth Symposium on Combinational Pattern Matching, Lecture Notes in Computer Science, 684 (1993) 179-196] proposed a new compact representation for suboptimal alignments. The kernel of that representation is a minimal directed acyclic graph (DAG) containing all suboptimal alignments. In this paper, a flexible space-saving scheme for computing such a DAG is proposed. In spite of the need for storing the DAG, these methods require very little additional working space. For two sequences of lengths M and N (M less than or equal to N), the general scheme runs in O(MN log(1/Upsilon)) time and O(M-Upsilon(M + N)) space for arbitrarily small 0 {$<$} Upsilon {$<$} 1. As a consequence, the worst-case running time is O(MN log log M) using only O(N) space. A variant of the method restricts the log log M factor to affect only grid points lying between suboptimal alignments. It is also shown that a running time of O(MN) can be achieved by using only O(M1+epsilon + N) space for arbitrarily small constant epsilon {$>$} 0. To exploit the computed DAG, a variant of Aho-Corasick pattern matching machine [A.V. Aho, M.J. Corasick, Comm. ACM 18 (1975) 333-340] is employed to locate all occurrences of specified patterns, and then a path is found in the DAG that maximizes the sum of the scores of the non-overlapping patterns occurring in it. An example illustrates the utility.}} @phdthesis{Cha-PhD-84, title = {{Design and Analysis of Graph Algorithms: Spanning Tree Enumeration, Planar Embedding and Maximal Planarization}}, author = {Rajagopalan Jayakumar}, school = {Concordia Univ., Dept. Electronics and Electrical Engineering}, year = {1984}, abstract = {In Part I of this thesis, a detailed computational complexity analysis of a spanning tree enumeration algorithm due to Char is given. An expression for the number of sequences generated by the algorithm when applied on a general graph is derived. The complexity of this algorithm is shown to be $O(n^3 t)$ where $n$ is the number of vertices of the graph and $t$ is the number of spanning trees. Two heuristics aimed at reducing the number of sequences generated are proposed for selecting the initial spanning tree and an implementation using path compression is described. A class of special graphs for which the algorithm is of complexity $O(nt)$ is identified. Certain interesting results relating to the complete graph, the ladder, and the wheel, which belong to this class, are obtained. An efficient implementation of Char's algorithm, called algorithm MOD-CHAR, is developed. Classes of graphs for which algorithm MOD-CHAR is of complexity $O(nt)$ are identified. It is shown that for large complete graphs ($n\ge 8$), algorithm MOD-CHAR requires, on the average, at most 10 computational steps to generate a spanning tree. A computational evaluation of Char's algorithm in comparison with Gabow and Myers' algorithm is presented. In Part II, efficient algorithms to obtain a planar embedding of a planar graph and to determine a maximal planar subgraph of a nonplanar graph are developed. An embedding procedure which involves placing the vertices at different horizontal and vertical levels in the plane is developed. The vertical levels of the vertices are decided by their st-numbers and an $O(n)$ algorithm is presented to determine the horizontal levels of the vertices. Another $O(n)$ algorithm to determine the order in which edges entering a vertex from lower numbered vertices should be drawn is developed. A procedure to draw by hand the edges without crossovers is described. It is shown that a planarization algorithm due to Ozawa and Takahashi does not, in general, determine a maximal planar subgraph. A new maximal planarization algorithm of complexity $O(n^2)$ is developed.}} @article{ChaMil-Algo-95, title = {{Linear-space algorithms that build local alignments from fragments}}, author = {Kun-Mao Chao and Webb Miller}, journal = {Algorithmica}, volume = {13}, pages = {106--134}, year = {1995}, review = {MR-95j-92011}} @article{MR-95j-92011, reviews = {ChaMil-Algo-95}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Linear-space algorithms that build local alignments from fragments}}, author = {Dietmar Dorninger}, volume = {95j}, number = {92011}, year = {1995}, text = {Given two sequences $A=a\sb 1,a\sb 2,\cdots,a\sb M$ and $B=b\sb 1,b\sb 2,\cdots,b\sb N$, a fragment $f=(i,j,k)$ is defined by $a\sb i=b\sb j$, $a\sb {i+1}=b\sb {j+1},\cdots,a\sb {i+k-1}=b\sb {j+k-1}$ and the property that $f$ is not properly contained in another fragment. The set $F$ of all fragments in respect to $A$ and $B$ can be partially ordered by the relation $(i,j,k)<(i',j',k')$ iff $i'+k'\leq i$ and $j'+k'\leq j$. An alignment is a sequence $f\sb 1,f\sb 2,\cdots,f\sb r$ in $F$ with $f\sb i>f\sb {i+1}$ for $i=1,2,\cdots,r-1$. By assigning scores to fragments and gaps, the question arises as to how to find an alignment for which the sum of fragment scores minus penalties for gaps is highest. By assuming affine gap functions and combining a time efficient dynamic programming method with a space saving approach, the authors develop an alignment algorithm that uses $O((M+N+\vert F\vert \log N)\log M)$ time and $O(M+N)$ storage. By removing all fragments of a highest scoring alignment from $F$ and determining a highest scoring alignment from the fragments remaining in $F$, and by further repeating this procedure, one obtains the $n$ best nonintersecting alignments. A time efficient algorithm using linear space to compute the $n$ best nonintersecting alignments for preassigned $n$ is constructed and the utility of it is demonstrated by an example from DNA-comparison.}} @article{Che-COR-93, title = {{An algorithm for finding the $k$ quickest paths in a network}}, author = {Yen-Liang Chen}, journal = {Computers and Operations Research}, volume = {20}, pages = {59--65}, year = {1993}, abstract = {Let $N$ be a network with n nodes and m arcs, and let $\sigma$ be the amount of data to be transmitted. The quickest path problem is to find a routing path in $N$ such that the time required to ship $\sigma$ units of data from the source to the sink is minimum. The problem considered is to find the first $k$ quickest looping paths from the source to the sink, and an algorithm with time complexity of $O(m^2+(m+k)n\log{n}+k^{3/2}\log{k})$ is developed.}} @article{Che-IPL-94, title = {{Finding the $k$ quickest simple paths in a network}}, author = {Yen-Liang Chen}, journal = {Information Processing Letters}, volume = {50}, pages = {89--92}, year = {1994}} @article{CheHam-DAM-87, title = {{Algorithms for finding $K$-best perfect matchings}}, author = {Chandra R. Chegireddy and Horst W. Hamacher}, journal = {Discrete Applied Mathematics}, volume = {18}, pages = {155--165}, year = {1987}, review = {MR-89j-90209}} @article{MR-89j-90209, reviews = {CheHam-DAM-87}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Algorithms for finding $K$-best perfect matchings}}, volume = {89j}, number = {90209}, year = {1989}, text = {In the $K$-best perfect matching problem $(K{\rm M})$ one wants to find $K$ pairwise different, perfect matchings $M\sb 1,\cdots,M\sb K$ such that $w(M\sb 1)\ge w(M\sb 2)\ge\cdots\ge w(M\sb K)\ge w(M)$, for all $M\not= M\sb 1,M\sb 2,\cdots,M\sb K$. The procedure discussed in this paper is based on a binary partitioning of the matching solution space. We survey different algorithms to perform this partitioning. The best complexity bound of the resulting algorithms discussed is $O(Kn\sp 3)$, where $n$ is the number of nodes in the graph.}} @article{CheHun-COR-94, title = {{Algorithms for the constrained quickest path problem and the enumeration of quickest paths}}, author = {G.-H. Chen and Y.-C. Hung}, journal = {Computers and Operations Research}, volume = {21}, pages = {113--118}, year = {1994}, abstract = {The quickest path problem, originally proposed by Chen and Chin (1989), is a variant of the shortest path problem. Its objective is to find quickest paths in a network to transmit a given amount of data such that the transmission time is minimized. If the quickest paths are required to go through a specified path, then the restricted problem is called the constrained quickest path problem. In this paper, for all pairs of nodes in a network $N$, an $O(mn^2)$ time algorithm is first presented to find constrained quickest paths, and then an $O(k^2mn^2)$ time algorithm is presented to enumerate the first $k$ quickest paths. The results improve previous results by Rosen, Sun and Xue (1991).}} @techreport{CheRinTan-WP-97, title = {{The first $K$ minimum time paths in a time-schedule network}}, author = {Yen-Liang Chen and Dan Rinks and Kwei Tang}, type = {Working Paper}, institution = {Louisiana State Univ., Dept. of Information Systems and Decision Sciences}, number = {9708}, year = {1997}, url = {http://www.bus.lsu.edu/isds/chun/wpapers/9708.htm}, abstract = {The time-constrained shortest path problem is an important generalization of the shortest path problem and has attracted much research interest in recent years. In this paper, we consider a time constraint commonly encountered in practice; namely, time-schedule constraint, which assumes that every node in the network has a list of pre-specified departure times and requires that departure from a node take place only at one of the departure times. Two problems associated with the first K minimum time paths in a time-schedule network are considered. The first is to find the first K loopless minimum time paths, in which all the nodes in a path are distinct, and the second is to find the first K minimum time looping paths, in which a path may pass through some nodes more than one time. For both problems, efficient polynomial time algorithms are developed.}} @inproceedings{CheSoo-ASSP-94, title = {{An $N$-best candidates-based discriminative training for speech recognition applications}}, author = {Jung-Kuei Chen and F. K. Soong}, booktitle = {Proc. Int. Conf. Acoustics, Speech, and Signal Processing}, publisher = {IEEE}, volume = {1}, pages = {I/625--628}, month = {April}, year = {1994}} @article{CheSoo-TSAP-94, title = {{An $N$-best candidates-based discriminative training for speech recognition applications}}, author = {Jung-Kuei Chen and F. K. Soong}, journal = {Trans. Speech {\&} Audio Processing}, publisher = {IEEE}, volume = {2}, number = {1, part 2}, pages = {206--216}, month = {January}, year = {1994}, abstract = {The authors propose an $N$-best candidates-based discriminative training procedure for constructing high-performance HMM speech recognizers. The algorithm has two distinct features: $N$-best hypotheses are used for training discriminative models; and a new frame-level loss function is minimized to improve the separation between the correct and incorrect hypotheses. The $N$-best candidates are decoded based on their recently proposed tree-trellis fast search algorithm. The new frame-level loss function, which is defined as a halfwave rectified log-likelihood difference between the correct and competing hypotheses, is minimized over all training tokens. The minimization is carried out by adjusting the HMM parameters along a gradient descent direction. Two speech recognition applications have been tested, including a speaker independent, small vocabulary (ten Mandarin Chinese digits), continuous speech recognition, and a speaker-trained, large vocabulary (5000 commonly used Chinese words), isolated word recognition. Significant performance improvement over the traditional maximum likelihood trained HMMs has been obtained. In the connected Chinese digit recognition experiment, the string error rate is reduced from 17.0 to 10.8{\%} for unknown length decoding and from 8.2 to 5.2{\%} for known length decoding. In the large vocabulary, isolated word recognition experiment, the recognition error rate is reduced from 7.2 to 3.8{\%}. Additionally, they have found that using more relaxed decoding constraints in preparing $N$-best hypotheses yields better recognition results.}} @inproceedings{CheSooLee-ASSP-94, title = {{Large vocabulary word recognition based on tree-trellis search}}, author = {Jung-Kuei Chen and F. K. Soong and Lin-Shan Lee}, booktitle = {Proc. Int. Conf. Acoustics, Speech, and Signal Processing}, publisher = {IEEE}, volume = {2}, pages = {II/137--140}, month = {April}, year = {1994}, abstract = {In this paper we propose a large vocabulary (90000 words), Chinese (Mandarin) word recognizer based on the tree-trellis fast search algorithm. The recognizer is divided into 3 modules: local likelihood computation, a forward trellis search and a backward tree search. In the forward trellis search, a free syllable decoding is performed without a language model and a partial path map is created. The best-first tree search is then applied backward along a lexicon, which is arranged as a syllabic tree, to find the $N$-best word candidates. In the experiment, context-dependent subsyllabic HMMs were trained with a new discriminative training method. When it is evaluated on a speaker-trained database, the recognizer achieved a word error rate of 5{\%} for the full size (90000 words) vocabulary and 1.7{\%} for a smaller subset (5000 words) vocabulary. A real-time demo system has also been implemented on an SGI R-4000 workstation.}} @article{ChiChe-CSSE-97, title = {{Block-switch networks: a cost-effective class of interconnection networks}}, author = {Wei-Kuo Chiang and Rong-Jaye Chen}, journal = {Computer Systems Science and Engineering}, volume = {12}, number = {3}, pages = {175--185}, month = {May}, year = {1997}, abstract = {A new interconnection scheme is proposed for hierarchically constructing massively parallel systems, called the block-switch network (BSN). The authors present a method of connecting together a number of identical basic atoms level by level, a basic atom being an arbitrary connected graph. A BSN is characterized by (G,m), where G represents the basic atom and m denotes the number of levels in hierarchical expansion. A particular choice for G yields a family of hierarchical networks. The topological properties of the BSN for the general case are investigated, and then the results gained from applying BSN to different basic atoms are also discussed. The BSN enables us to construct new families of graphs more feasible and cost-effective. A shortest-path routing algorithm for the BSN is derived by reducing the routing problem to the K-best perfect matching problem. In particular the authors implement fundamental parallel algorithms (descend/ascend) on the BSN(Q/sub n/,m) where Q/sub n/ denotes an n-cube, and demonstrate that the performance on the BSN(Q/sub n/,m) is very close to that of the comparable hypercube.}} @article{ChoBur-TPAS-84, title = {{Transmission line route selection: An application of $K$-shortest paths and goal programming}}, author = {F. Choobineh and T. Burgman}, journal = {Trans. Power Apparatus and Systems}, publisher = {IEEE}, volume = {PAS-103}, pages = {3253--3259}, year = {1984}, abstract = {A two-stage solution procedure is developed as a managerial decision-making tool in the transmission line route selection process. In stage one, the K least costly alternatives are found, based strictly on monetary considerations. In stage two, the alternative which causes the least amount of social and environmental disruption is selected from the alternatives generated in stage one.}} @article{ChoLeeJua-PRAI-94, title = {{A minimum error rate pattern recognition approach to speech recognition}}, author = {W. Chou and C.-H. Lee and B.-H. Juang and F. K. Soong}, journal = {Int. J. Pattern Recognition {\&} Artificial Intelligence}, volume = {8}, number = {1}, pages = {5--31}, month = {February}, year = {1994}, abstract = {In this paper, a minimum error rate pattern recognition approach to speech recognition is studied with particular emphasis on the speech recognizer designs based on hidden Markov models (HMMs) and Viterbi decoding. This approach differs from the traditional maximum likelihood based approach in that the objective of the recognition error rate minimization is established through a specially designed loss function, and is not based on the assumptions made about the speech generation process. Various theoretical and practical issues concerning this minimum error rate pattern recognition approach in speech recognition are investigated. The formulation and the algorithmic structures of several minimum error rate training algorithms for an HMM-based speech recognizer are discussed. The tree-trellis based $N$-best decoding method and a robust speech recognition scheme based on the combined string models are described. This approach can be applied to large vocabulary, continuous speech recognition tasks and to speech recognizers using word or subword based speech recognition units. Various experimental results have shown that significant error rate reduction can be achieved through the proposed approach.}} @inproceedings{ChoMadMor-ICCI-95, title = {{On finding single-source single-destination $k$ shortest paths}}, author = {Eugene Inseok Chong and Sanjeev Rao Maddila and Steven Todd Morley}, booktitle = {Proc. 7th Int. Conf. Computing and Information}, month = {July}, year = {1995}, url = {http://phoenix.trentu.ca/jci/papers/icci95/A206/P001.html}, abstract = {The shortest path algorithms have a wide range of applications and much research has been devoted to the subject. While finding a shortest path in a digraph is relatively easy, finding $k$ shortest paths is not an easy task, especially for a single-source and single-destination pair. In this paper, we present an algorithm for finding $k$ shortest paths for a source-destination pair. Our algorithm is applicable to any digraphs without negative weights. The paths are not necessarily simple, but if the digraphs are acyclic, the paths found will be simple. Given a digraph of $n$ vertices and $m$ edges, our algorithm runs in time $O(km\log(kn)+k^2m)$ and space $O(kn)$. Our algorithm is an extension of Dijkstra's algorithm, easy to implement, and generates the $k$ shortest paths in the order of the path length.}} @inproceedings{ChoMatJua-ASSP-94, title = {{An algorithm of high resolution and efficient multiple string hypothesization for continuous speech recognition using inter-word models}}, author = {W. Chou and T. Matsuoka and B.-H. Juang and C.-H. Lee}, booktitle = {Proc. Int. Conf. Acoustics, Speech, and Signal Processing}, publisher = {IEEE}, volume = {2}, pages = {II/153--156}, month = {April}, year = {1994}, abstract = {We propose a new accurate string hypothesization algorithm to find the $N$-best multiple string hypotheses in continuous speech recognition. The algorithm differs from the conventional $N$-best search algorithms in that it allows the use of the same set of long term language model scores and the detailed context-dependent subword models such as inter-word context dependent triphone models in both forward and backward search for high performance speech recognition. It is an extension of the tree-trellis $N$-best search algorithm(1). The inter-word context dependency is exactly preserved in both forward partial path map preparation and the proposed backward $N$-best multiple string hypothesis tree search. The search efficiency is maximized by applying the same high resolution acoustic and language models in both search directions. When search heuristics are used, the proposed approach provides a more accurate string model matching than that of the conventional frame-synchronous Viterbi beam search decoder.}} @inproceedings{ChoSch-SNLW-89, title = {{The $N$-best algorithm: an efficient search procedure for finding top $N$ sentence hypotheses}}, author = {Yen-Lu Chow and Richard Schwartz}, booktitle = {Proc. DARPA Speech {\&} Natural Language Worksh.}, pages = {199--202}, year = {1989}} @inproceedings{Chu-RECOMB-97, title = {{Monte Carlo sequence alignment}}, author = {Gary A. Churchill}, booktitle = {Proc. 1st Int. Conf. Computational Molecular Biology}, publisher = {ACM}, pages = {93--97}, month = {January}, year = {1997}, summary = {Extracted from various points in this paper (which lacks an abstract): ``The alignment of molecular sequences is a problem central to many important questions in molecular biology. ... The problem studied here lies at the intersection of two lines of research. The first is concerned with the sensitivity of alignments to choice of scores. ... A second line of research is the study of suboptimal alignments. This work has been driven by the observation that an optimal alignment is not necessarily a biologically correct alignment. However, biologically correct alignments are often nearly optimal when the scoring system is well chosen. A recent review of suboptimal alignment methods is provided by Vingron [Vin-COSB-96]. ... Our goal in this work is to develop algorithms to sample from the marginal posterior distribution of an alignment. ... Pairwise alignments can be represented as a directed graph on a two dimensional grid ... An alignment is shown as a path, a connected sequence of arcs, traversing the matrix from the upper left vertex to the lower right vertex by a series of east, southeast, and south moves. ... The algorithm employed to sample from the distribution is similar in style to standard dynamic programming. A forward pass through the matrix is used to compute conditional probabilities for partial alignments that end with each node in the path graph. However, instead of choosing the optimal score at each step, our algorithm sums over the three arcs entering the node.''}} @article{ClaKriRau-SIAM-63, title = {{Computing the $N$ best loopless paths in a network}}, author = {S. Clarke and A. Krikorian and J. Rausen}, journal = {J. SIAM}, publisher = {SIAM}, volume = {11}, pages = {1096--1102}, year = {1963}} @article{ColDayNel-Algs-89, title = {{Unranking and ranking spanning trees of a graph}}, author = {Charles Joseph Colbourn and R. P. J. Day and L. D. Nel}, journal = {J. Algorithms}, volume = {10}, number = {2}, pages = {271--286}, month = {June}, year = {1989}, abstract = {The set $S$ of spanning trees of an $n$-vertex graph $G$ can be placed in one-to-one correspondence with the interval $(1,s)$ where $s=|S|$. The authors develop $O(n^3)$ unranking and ranking functions for the spanning trees of an arbitrary graph. The unranking function maps any interval $(1,s)$ to the corresponding tree, while the ranking function maps a spanning tree to the appropriate index in the interval. The unranking function provides an $O(n^3)$ method for generating a random spanning tree of a graph with uniform distribution.}, review = {MR-90g-68060}} @article{MR-90g-68060, reviews = {ColDayNel-Algs-89}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Unranking and ranking spanning trees of a graph}}, volume = {90g}, number = {68060}, year = {1990}} @article{ColMyrNeu-Algs-96, title = {{Two algorithms for unranking arborescences}}, author = {Charles Joseph Colbourn and Wendy J. Myrvold and Eugene Neufeld}, journal = {J. Algorithms}, volume = {20}, number = {2}, pages = {268--281}, year = {1996}, abstract = {Colbourn, Day, and Nel developed the first algorithm requiring at most $O(n^3)$ arithmetic operations for ranking and unranking spanning trees of a graph ($n$ is the number of vertices of the graph). We present two algorithms for the more general problem of ranking and unranking rooted spanning arborescences of a directed graph. The first is conceptually very simple and requires $O(n^3)$ arithmetic operations. The second approach shows that the number of arithmetic operations can be reduced to the same as that of the best known algorithms for matrix multiplication.}, review = {MR-97d-68154}} @article{MR-97d-68154, reviews = {ColMyrNeu-Algs-96}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Two algorithms for unranking arborescences}}, volume = {97d}, number = {68154}, year = {1997}} @inproceedings{ConPec-AIRO-95, title = {{Using simulated annealing to solve the $K$-shortest path problem}}, author = {Andrea Consiglio and Antonio Pecorella}, booktitle = {Proc. AIRO 1995}, publisher = {Associazione Italiana Ricerca Operativa}, month = {September}, year = {1995}} @article{CouCliCur-COR-99, title = {{An interactive bi-objective shortest path approach: searching for unsupported nondominated solutions}}, author = {J. M. Coutinho-Rodrigues and J. C. N. Cl{\'\i}maco and John Richard Current}, journal = {Computers and Operations Research}, volume = {26}, number = {8}, pages = {789--798}, month = {July}, year = {1999}, abstract = {In many network routing problems, several conflicting objectives must be considered. Even for the bi-objective shortest path problem, generating and presenting the whole set of nondominated solutions (paths) to a decision maker, in general, is not effective because the number of these paths can be very large. Interactive procedures are adequate to overcome these drawbacks. J.R. Current et al. (1990) proposed an interactive approach based on a NISE-like procedure (J. Cohon, 1978) to search for nondominated supported solutions and using auxiliar constrained shortest path problems to carry out the search inside the duality gaps. We propose a new interactive approach to search for unsupported nondominated solutions (lying inside duality gaps) based on a k-shortest path procedure. Both approaches are compared.}} @inproceedings{CoxHin-ICPR-94, title = {{An efficient implementation of Reid's multiple hypothesis tracking algorithm and its evaluation for the purpose of visual tracking}}, author = {Ingemar J. Cox and S. L. Hingorani}, booktitle = {Proc. 12th Int. Conf. Pattern Recognition}, publisher = {IEEE}, volume = {1}, pages = {437--442}, year = {1994}, abstract = {An efficient implementation of Reid's multiple hypothesis tracking (MHT) algorithm is presented in which the the k-best hypotheses are determined in polynomial time using an algorithm due to Murty (1968). The MHT algorithm is then applied to several motion sequences. The MHT capabilities of track initiation, termination and continuation are demonstrated. Continuation allows the MHT to function despite temporary occlusion of tracks. Between 50 and 150 corner features are simultaneously tracked in the image plane over a sequence of up to 60 frames. Each corner is tracked using a simple linear Kalman filter and any data association uncertainty is resolved by the MHT. Kalman filter parameter estimation is discussed and experimental results show that the algorithm is robust to errors in the motion model.}} @article{CoxHin-PAMI-96, title = {{An efficient implementation of Reid's multiple hypothesis tracking algorithm and its evaluation for the purpose of visual tracking}}, author = {Ingemar J. Cox and S. L. Hingorani}, journal = {Trans. Pattern Analysis and Machine Intelligence}, publisher = {IEEE}, volume = {18}, pages = {138--150}, year = {1996}, abstract = {An efficient implementation of Reid's multiple hypothesis tracking (MHT) algorithm is presented in which the k-best hypotheses are determined in polynomial time using an algorithm due to Murly (1968). The MHT algorithm is then applied to several motion sequences. The MHT capabilities of track initiation, termination, and continuation are demonstrated together with the latter's capability to provide low level support of temporary occlusion of tracks. Between 50 and 150 corner features are simultaneously tracked in the image plane over a sequence of up to 51 frames. Each corner is tracked using a simple linear Kalman filter and any data association uncertainty is resolved by the MHT. Kalman filter parameter estimation is discussed, and experimental results show that the algorithm is robust to errors in the motion model. An investigation of the performance of the algorithm as a function of look-ahead (tree depth) indicates that high accuracy can be obtained for tree depths as shallow as three. Experimental results suggest that a real-time MHT solution to the motion correspondence problem is possible for certain classes of scenes.}} @article{CoxMil-TAES-95, title = {{On finding ranked assignments with application to multitarget tracking and motion correspondence}}, author = {Ingemar J. Cox and Matt L. Miller}, journal = {Trans. Aerospace and Electronic Systems}, publisher = {IEEE}, volume = {31}, pages = {486--489}, year = {1995}, abstract = {Within the target tracking community there is strong interest in computing a ranked set of assignments of measurements to targets. These k-best assignments are then used to determine good approximations to the data association problem. Much earlier work described algorithms which either had exponential worst case time or were not guaranteed to return the k-best assignments. Danchick and Newnam (1993) described a fast algorithm for finding the exact k-best hypotheses. However, in the worst case, k! linear assignment problems must be solved. This correspondence describes an algorithm originally due to Murty (1968) for optimally determining a ranked set of assignments in polynomial time and which is linear in k.}} @article{CoxMilDan-TAES-97, title = {{A comparison of two algorithms for determining ranked assignments with application to multitarget tracking and motion correspondence}}, author = {Ingemar J. Cox and Matt L. Miller and R. Danchick and G. E. Newnam}, journal = {Trans. Aerospace and Electronic Systems}, publisher = {IEEE}, volume = {33}, number = {1}, pages = {295--301}, month = {January}, year = {1997}, abstract = {Recently, it has become clear that determining a ranked set of assignments allows computation of very good approximations to the data association problem. Several algorithms have been proposed but only two return the k-best assignments in reasonable time. One is Danchick and Newnams' [1993] algorithm, which is based on the recognition that determining the best assignment is a classical assignment problem and that determining a ranked set of assignments may be accomplished by solving a series of modified copies of the initial assignment problem. The other algorithm is originally due to Murty [1968] and was most recently described within the context of multitarget tracking. We evaluate the two algorithm using randomly generated data and data obtained from an electrooptical sensor simulation in which 90 missiles are launched. These evaluations show that Murty's algorithm perform significantly better in all scenarios. We show the relationship between the two algorithms and how Danchick and Newnam's algorithm can be very easily modified to Murty's algorithm. Experimental results using Murty's algorithm suggest that a solution to the real-time data association problem is now feasible.}} @article{CurReVCoh-TS-87, title = {{The median shortest path problem: a multiobjective approach to analyze cost vs. accessibility in the design of transportation networks}}, author = {John Richard Current and Charles S. ReVelle and Jared Leigh Cohon}, journal = {Transportation Science}, volume = {21}, number = {3}, pages = {188--197}, year = {1987}, review = {MR-88h-90067}} @article{MR-88h-90067, reviews = {CurReVCoh-TS-87}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{The median shortest path problem: a multiobjective approach to analyze cost vs. accessibility in the design of transportation networks}}, volume = {88h}, number = {90067}, year = {1988}, text = {We introduce the median shortest path problem (MSPP). The MSPP is a bicriterion path problem with the objectives being the minimization of the total path length and the minimization of the total travel time required for demand to reach a node on the path. Potential applications of the MSPP include, among others, the location of new highways, railroad lines and subway lines and the design of airline routes. It is particularly applicable in transportation network design problems where the trade-off between operator costs and user costs is important. An algorithm is presented to identify noninferior solutions to the MSPP. This algorithm incorporates a $K$ shortest path algorithm. The algorithm is demonstrated with a sample problem and the results are compared to those obtained using integer programming.}} @inproceedings{DaiImaIwa-ISAAC-93, title = {{How to treat delete requests in semi-online problems}}, author = {Yang Dai and Hiroshi Imai and Kazuo Iwano and Naoki Katoh}, booktitle = {Proc. 4th Int. Symp. Algorithms and Computation}, number = {762}, series = {Lecture Notes in Computer Science}, publisher = {Springer Verlag}, pages = {48--57}, year = {1993}, abstract = {We propose a new approach to obtain a semi-online fully dynamic algorithm, given a partially dynamic algorithm, by introducing a new way of handling delete requests. Briefly speaking, we are interested in how online algorithms become more efficient with some partial knowledge of future delete requests. A dynamic algorithm solves the problem for the current instance every time when an add/delete request is made to change the instance. If a dynamic algorithm allows only add requests, we call it partially dynamic, otherwise we call it fully dynamic. An offline algorithm gives a set of solutions of a dynamic algorithm when the entire request sequence is known beforehand. A semi-online problem is a special case of online problems.}} @inproceedings{DaiLee-ICCC-94, title = {{Parsing with tag information in a probabilistic generalized LR parser}}, author = {Jian-Cheng Dai and Hsi-Jian Lee}, booktitle = {Proc. Int. Conf. Chinese Computing}, publisher = {Nat. Univ. Singapore}, pages = {33--39}, month = {June}, year = {1994}, abstract = {A new corpus-based probabilistic generalized LR parser is presented for parsing Chinese sentences. Because there are generally different tags in each word of a Chinese sentence, it is helpful to use tag information to avoid parsing tag sequences that are unreliable with respect to a particular input sentence. In order to use tag information conveniently, a multi-stage input graph is constructed to represent the $N$-best tag sequences. In the proposed parser, parse paths are formulated as a sentence transition graph. The parser, which applies a sentence merging technique and a hill climbing strategy, truncates unpromising partial parses quickly. Experimental results reveal that the hill climbing strategy is more efficient than the depth-first strategy and the proposed sentence merging technique is also effective.}} @article{DanNew-TAES-93, title = {{A fast method for finding the exact $N$-best hypotheses for multitarget tracking}}, author = {R. Danchick and G. E. Newnam}, journal = {Trans. Aerospace and Electronic Systems}, publisher = {IEEE}, volume = {29}, pages = {555--560}, year = {1993}, abstract = {The necessity for multiple hypothesis tracking (MHT) is recognized throughout the SDI tracking community. However, implementations of MHT techniques have required enormous amounts of computer time and memory. An efficient method of measurement-to-target association that makes MHT practical for the first time is presented. The method finds the exact N-best feasible hypotheses directly from a sequence of linear assignment problem solutions.}} @inproceedings{Das-ICCS-85, title = {{On search strategies for $n$ best solutions}}, author = {Das Gupta, S.}, booktitle = {Int. Conf. Cybernetics {\&} Society}, publisher = {IEEE}, pages = {664--668}, month = {November}, year = {1985}, abstract = {Search strategies of various types and forms are used to find optimal solutions to problems in different areas to determine the 'best' solution. In many situations it is desirable to have a collection of n best solutions sorted on cost rather than having the unique optimal solution. There are many heuristic search strategies in the artificial intelligence problems where combinatorial explosion makes the search for the optimal infeasible. In some cases it is possible to break the problem into subproblems, obtain n-best solutions and then synthesize the problem into an n-best solution for the whole problem. The author proposes some search strategies for n-best solution in closed form and using heuristics.}} @inproceedings{DeaKelLih-GTCA-92, title = {{The spanning tree enumeration problem for digraphs}}, author = {Nathaniel Dean and A. K. Kelmans and Keh-Wei Lih and William A. Massey and Peter Winkler}, booktitle = {Graph Theory, Combinatorics, and Algorithms}, pages = {277--287}, year = {1992}} @inproceedings{DenNuSam-ASSP-95, title = {{Improved speech modeling and recognition using multi-dimensional articulatory states as primitive speech units}}, author = {L. Deng and J. Nu and H. Sameti}, booktitle = {Proc. Int. Conf. Acoustics, Speech, and Signal Processing}, publisher = {IEEE}, volume = {1}, pages = {385--388}, month = {May}, year = {1995}, abstract = {We provide a formal description of a speech recognizer designed on the basis of elaborate articulatory timing that a asynchronous across the multiple articulatory-feature dimensions. Three improved critical components of the recognizer are described in detail. Evaluation results, obtained from a standard TIMIT phonetic recognition task confined within the $N$-best rescoring scenario, are reported on comparative performances between the new feature-based recognizer and a recognizer using the conventional context-dependent triphone units. The results demonstrate an overall superior quality of the rescored $N$-best list from the feature-based recognizer over that from the triphone-based recognizer. Greater performance improvements are observed as the top number of candidate sentences increases.}} @article{Der-DAM-85, title = {{Some basic exchange properties in combinatorial optimization and their application to constructing the $k$-best solutions}}, author = {Ulrich Derigs}, journal = {Discrete Applied Mathematics}, volume = {11}, pages = {129--141}, year = {1985}, review = {MR-86m-90124}} @article{MR-86m-90124, reviews = {Der-DAM-85}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Some basic exchange properties in combinatorial optimization and their application to constructing the $k$-best solutions}}, author = {Th. M. Liebling}, volume = {86m}, number = {90124}, year = {1986}, text = {We characterize optimal, $k$-best and sets of $k$-best solutions for a combinatorial optimization problem via simple exchange properties. We show the relationship of this concept to the concept of adjacency and we extend the concept to discrete optimization problems and problems with objective functions fulfilling the cone-property. We show that those exchange properties play a fundamental role in partitioning strategies for finding sets of $k$-best solutions.}} @inproceedings{Der-ICOR-84, title = {{Exchange properties and $K$-best strategies in combinatorial optimization}}, author = {Ulrich Derigs}, booktitle = {Proc. 10th Int. Conf. Operational Research}, publisher = {North-Holland}, pages = {393--406}, year = {1984}, abstract = {Exchange properties in set systems underlying combinatorial optimizations problems play an important role in characterising best and next best solutions and in partitioning strategies for ranking the set of feasible solutions. The author exploits these basic combinatorial principles and shows their application for some standard problems.}} @inproceedings{DesPicKao-SSST-95, title = {{Efficient search strategies in hierarchical pattern recognition systems}}, author = {N. Deshmukh and J. Picone and Yu-Hung Kao}, booktitle = {Proc. 27th Southeastern Symp. System Theory}, publisher = {IEEE}, pages = {88--91}, month = {March}, year = {1995}, abstract = {We describe the generalized $N$-best search algorithm as applied to hierarchical pattern recognition, and discuss its limitations for a broad class of problems. We then introduce a new algorithm, called the Frame-Synchronous Viterbi Search, that prunes hypotheses by actively organizing system memory after each step in the search. This algorithm is shown to save memory and computation for a specific class of problems involving large search spaces and small memory resources. We also discuss generalizations of this algorithm to provide true N-best scoring and intelligent pruning while preserving the hierarchical structure of the hypotheses. An example of a practical speech recognition system using this algorithm is given.}} @article{DicDrySac-IJCGA-92, title = {{Simple algorithms for enumerating interpoint distances and finding $k$ nearest neighbors}}, author = {Matthew T. Dickerson and R. L. Scot Drysdale and J{\"o}rg-Rudiger Sack}, journal = {Int. J. Computational Geometry and Applications}, volume = {2}, number = {3}, pages = {221--239}, year = {1992}, review = {MR-93j-68212}} @article{MR-93j-68212, reviews = {DicDrySac-IJCGA-92}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Simple algorithms for enumerating interpoint distances and finding $k$ nearest neighbors}}, volume = {93j}, number = {68212}, year = {1993}, text = {We present an $O(n\log n+k\log k)$ time and $O(n+k)$ space algorithm which takes as input a set of $n$ points in the plane and enumerates the $k$ smallest distances between pairs of points in nondecreasing order. We also present an $O(n\log n+kn\log k)$ solution to the problem of finding the $k$ nearest neighbors for each of $n$ points. Both algorithms are conceptually very simple, are easy to implement, and are based on a common data structure: the Delaunay triangulation. Variants of the algorithms work for any convex distance function metric.}} @article{DicEpp-CGTA-96, title = {{Algorithms for proximity problems in higher dimensions}}, author = {Matthew T. Dickerson and David Eppstein}, journal = {Computational Geometry Theory and Applications}, volume = {5}, pages = {277--291}, year = {1996}, abstract = {We present algorithms for five interdistance enumeration problems that take as input a set $S$ of $n$ points in $R^d$ (for a fixed but arbitrary dimension $d$) and as output enumerate pairs of points in $S$ satisfying various conditions. We present: an $O(n\log{n}+k)$ time and $O(n)$ space algorithm that takes as additional input a distance $\delta$ and outputs all $k$ pairs of points in $S$ separated by a distance of $\delta$ or less; an $O(n\log{n}+k\log{k})$ time and $O(n+k)$ space algorithm that enumerates in non-decreasing order the $k$ closest pairs of points in $S$; an $O(n\log{n}+k)$ time algorithm for the same problem without any order restrictions; an $O(nk\log{n})$ time and $O(n)$ space algorithm that enumerates in nondecreasing order the $nk$ pairs representing the $k$ nearest neighbors of each point in $S$; and an $O(n\log{n}+kn)$ time algorithm for the same problem without any order restrictions. The algorithms combine a modification of the planar approach of Dickerson, Drysdale, and Sack with the method of Bern, Eppstein, and Gilbert for augmenting a point set to have a linear size bounded degree Delaunay triangulation. Thus, in addition to providing new solutions to these problems, the paper also shows how the Delaunay triangulation can be used as the underlying data structure in a unified approach to proximity problems even in higher dimensions.}} @article{DioCliNor-IEE-89, title = {{Dynamic planning model for urban telephone networks and its applications}}, author = {J. M. B. Diogo and J. C. N. Cl{\'\i}maco and P. M. N. Nordeste and J. M. F. Craveirinha}, booktitle = {IEE Proceedings I (Communications, Speech and Vision)}, volume = {136}, pages = {283--290}, year = {1989}, abstract = {Describes a model (ARCOS) for dynamic planning of small- and medium-size urban telephone networks. The main innovative feature of the method is the fact that, by exploring the spatial decomposition of a simplified initial network, one is led to a network of tractable size in the sense that it is possible to schedule 'K-best' network expansions in time, represented on a decision graph obtained according to some heuristic simplifications. For the purpose of defining the network expansions from the decision graph adequate versions of the K-shortest-paths algorithm and of a dynamic programming algorithm were used. That is, in ARCOS one seeks to improve a type of algorithm for primary cable network planning as presented by Rapp by introducing a new heuristic method that seeks to optimise the dynamic evolution of the network topology together with the equipment capacity expansions. The actual version of the ARCOS model and its application to particular urban networks is described. The advantages and difficulties of the method are also discussed.}} @article{Dod-OR-84, title = {{Determining the $K$ most critical paths in PERT networks}}, author = {Bajis Mohammed Dodin}, journal = {Operations Research}, volume = {32}, pages = {859--877}, year = {1984}, abstract = {A fundamental problem in PERT networks is to identify a project's critical paths and its critical activities. The author defines the criticality index of a path as the probability that the duration of the path is greater than or equal to the duration of every other path in the network and define the criticality index of an activity as the sum of the criticality indices of the paths containing that activity. The most critical path or K most critical paths in a PERT network could be found by enumerating all the paths and calculating the corresponding criticality indices, both of which are burdensome tasks. The paper uses stochastic dominance to develop a procedure to identify the K most critical paths without using this path enumeration. The procedure has been applied to various sized PERT networks generated at random, and the results are found to be very close to those obtained by extensive Monte Carlo sampling.}} @phdthesis{Dod-PhD-82, title = {{On the Completion Time of Stochastic PERT Networks}}, author = {Bajis Mohammed Dodin}, school = {North Carolina State Univ., Dept. of Operations Research}, year = {1982}, abstract = {A stochastic PERT network is a directed acyclic network with $N$ nodes and $A$ arcs, where the arc lengths are independent random variables with known probability distribution functions. A fundamental problem in PERT networks is to determine the probability distribution function (pdf) of the realization time of the project completion time $T_N$. An equally important problem in PERT networks is to identify the activities and paths that are critical to the achievement of the project objectives. Determining the exact pdf of $T_N$ is difficult. In this thesis we develop two procedures to approximate such pdf's. The first procedure assumes the independence of the paths in PERT network. It starts at node 1 and proceeds sequentially to nodes $2, 3, \ldots$, until it finally reaches node $N$; at each node it approximates the pdf of its realization time. The second procedure uses the series-parallel decomposition to reduce the AN to only one activity starting at node 1 and ending in node $N$. The pdf of the duration of the equivalent activity $(1, N)$ approximates the pdf of the project completion time. In the second problem if the duration of each activity is constant, then it is relatively easy to identify the critical path(s) and activities. In contrast such an identification is very difficult in PERT network. In this dissertation we first define the concepts of critical path(s) and activities, then develop procedures to identify the criticality of every activity and the top $K$ critical paths. To be able to test the accuracy of the approximating procedures developed in this thesis, a random AN generator was developed to generate a network $G(N,A)$ at random from the space of all feasible networks with $N$ nodes and $A$ arcs; also, a crude Monte Carlo sampling model was developed to approximate the pdf's of the realization times of every node and the criticality measures of the activities and the paths. The developed procedures have been programmed and tested using ANs of sizes $\le G(50, 150)$.}} @inproceedings{Dre-JNM-68, title = {{An appraisal of some shortest path algorithms}}, author = {S. E. Dreyfus}, booktitle = {ORSA/TIMS Joint National Mtg.}, journal = {Bull. Operations Research Soc. of America}, volume = {16}, pages = {166}, year = {1968}, abstract = {Abstract only given substantially as follows. Several traditional problems involving the determination of shortest paths through discrete networks will be examined. To avoid special cases, it will generally be assumed that all nodes are directly connected to all other nodes. Good algorithms will be identified and credited, to the best of the speaker's knowledge, to their earlier originators. Also some erroneous or inefficient procedures will be exposed. While little new material is developed, it is hoped that the talk will shorten some listeners' paths through the shortest path literature.}} @article{Dre-OR-69, title = {{An appraisal of some shortest path algorithms}}, author = {S. E. Dreyfus}, journal = {Operations Research}, volume = {17}, pages = {395--412}, year = {1969}} @article{DubEpi-ARC-76, title = {{Search algorithm for optimal alternatives in automated-design problems}}, author = {Yu. A. Dubov and N. V. Epikhova}, journal = {Automation and Remote Control}, volume = {37}, pages = {1220--1225}, year = {1976}, note = {English translation of \cite{DubEpi-AT-76}}} @article{DubEpi-AT-76, title = {{Search algorithm for optimal alternatives in automated-design problems}}, author = {Yu. A. Dubov and N. V. Epikhova}, journal = {Avtomatika i Telemekhanika}, volume = {37}, pages = {95--100}, year = {1976}, note = {In Russian}} @article{DunGroMac-JSAC-94, title = {{Comparison of $k$-shortest paths and maximum flow routing for network facility restoration}}, author = {D. A. Dunn and Wayne Davy Grover and M. H. MacGregor}, journal = {J. Selected Areas in Communications}, publisher = {IEEE}, volume = {12}, pages = {88--99}, year = {1994}, abstract = {In the development of technologies for span failure restoration, a question arises about the restoration rerouting characteristics to be specified. In theory, maximal rerouting capacity is obtained with a maximum flow (Max Flow) criterion. However, rerouting that realizes the k-successively shortest link disjoint paths (KSP) may be faster, easier, and, in distributed implementation, more robust than a distributed counterpart for Max Flow. The issue is, therefore, what the restoration capacity penalty is if KSP is used instead of Max Flow. To explore this tradeoff, the authors present a comparative study of the effectiveness of KSP versus Max Flow as an alternative rerouting criteria in the context of transport network span restoration. The comparison applies to both centrally controlled and distributed restoration systems. Study methods include exhaustive span failure experiments on a range of network models, and parametric and analytical investigations for insight into the factors resulting in KSP versus Max Flow differences. The main finding is that KSP restoration capacity is more than 99.9{\%} of that from Max Flow in typical network models. The hypothesis is made that a generalized 'trap' topology is responsible for all KSP-Max Flow capacity differences. The hypothesis is tested experimentally and used to develop analytical bounds which agree well with observed results. These findings and data are relevant to standards makers and equipment developers in specifying and engineering future restorable networks.}} @article{Epp-BIT-92, title = {{Finding the $k$ smallest spanning trees}}, author = {David Eppstein}, journal = {BIT}, volume = {32}, number = {2}, pages = {237--248}, year = {1992}, review = {MR-94e-05082}} @article{MR-94e-05082, reviews = {Epp-BIT-92}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Finding the $k$ smallest spanning trees}}, author = {M. M. Sys{\l}o}, volume = {94e}, number = {05082}, year = {1994}, text = {Improved solutions for the problem of generating the $k$ smallest spanning trees in a graph and in the plane are presented. The algorithm for general graphs takes time $O(m\log\beta(m,n)+k\sp 2)$; for planar graphs this bound can be improved to $O(n+k\sp 2)$.}} @inproceedings{Epp-FOCS-94, title = {{Finding the $k$ shortest paths}}, author = {David Eppstein}, booktitle = {Proc. 35th Symp. Foundations of Computer Science}, publisher = {IEEE}, pages = {154--165}, year = {1994}} @article{Epp-IJCGA-93, title = {{Tree-weighted neighbors and geometric $k$ smallest spanning trees}}, author = {David Eppstein}, journal = {Int. J. Computational Geometry and Applications}, volume = {4}, number = {2}, pages = {229--238}, year = {1994}, review = {MR-95f-05028}} @article{MR-95f-05028, reviews = {Epp-IJCGA-93}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Tree-weighted neighbors and geometric $k$ smallest spanning trees}}, author = {Ding-Zhu Du}, volume = {95f}, number = {05028}, year = {1995}, text = {Given a set of $n$ points in the plane, construct $k$ different spanning trees that have the minimum total edge lengths among all possible spanning trees of the point set. This geometric $k$ smallest spanning trees problem was proposed by the author previously. In this paper, the author improves the time bounds for computing the optimal solution. In particular, the time is $O(n\log n\log k+k(\min(k,n))^{1/2}\log(k/n))$ in the Euclidean plane and $O(n\log n+n\log\log n\log k+k(\min(k,n))^{1/2}\log(k/n))$ in the rectilinear plane.}} @article{Epp-MER-95, title = {{Ten algorithms for Egyptian fractions}}, author = {David Eppstein}, journal = {Mathematica in Education and Research}, volume = {4}, number = {2}, pages = {5--15}, year = {1995}, url = {http://www.ics.uci.edu/~eppstein/numth/egypt/}, annote = {Includes an implementation in Mathematica of the algorithm of Waterman and Byers for listing all paths shorter than a given length bound \cite{ByeWat-OR-84}, and uses it as a heuristic for the NP-hard problem of, given a graph with colored edges, finding a shortest path using each color at most once. This heuristic is used in an algorithm for finding representations of a rational number as a sum of distinct unit fractions: the algorithm expands the rational number into a sequence of unit fractions using continued fractions, finds a graph the edges of which correspond to subsequences that sum to unit fractions, and forms the overall representation by finding a path in this graph.}} @inproceedings{Epp-SWAT-90, title = {{Finding the $k$ smallest spanning trees}}, author = {David Eppstein}, booktitle = {Proc. 2nd Scandinavian Worksh. Algorithm Theory}, number = {447}, series = {Lecture Notes in Computer Science}, publisher = {Springer Verlag}, pages = {38--47}, year = {1990}} @techreport{Epp-TR-92-77, title = {{Tree-weighted neighbors and geometric $k$ smallest spanning trees}}, author = {David Eppstein}, institution = {Univ. of California, Irvine, Dept. Information and Computer Science}, number = {92-77}, year = {1992}} @techreport{Epp-TR-94-26, title = {{Finding the $k$ shortest paths}}, author = {David Eppstein}, institution = {Univ. of California, Irvine, Dept. Information and Computer Science}, number = {94-26}, year = {1994}} @techreport{Epp-TR-95-52, title = {{Finding common ancestors and disjoint paths in DAGs}}, author = {David Eppstein}, institution = {Univ. of California, Irvine, Dept. Information and Computer Science}, number = {95-52}, year = {1995}, abstract = {We consider the problem of finding pairs of vertex-disjoint paths in a DAG, either connecting two given nodes to a common ancestor, or connecting two given pairs of terminals. It was known how to find a single pair of paths, for either type of input, in polynomial time. We show how to find the $k$ pairs with shortest combined length, in time $O(mn + k)$. We also show how to count all such pairs of paths in $O(mn)$ arithmetic operations. These results can be extended to finding or counting tuples of $d$ disjoint paths, in time $O(mn^{d-1} + k)$ or $O(mn^{d-1})$. We give further results on finding the subset of the DAG involved in pairs of disjoint paths, and on finding disjoint paths in linear space.}} @inproceedings{EppGalIta-FOCS-92, title = {{Sparsification -- A technique for speeding up dynamic graph algorithms}}, author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Amnon Nissenzweig}, booktitle = {Proc. 33rd Symp. Foundations of Computer Science}, publisher = {IEEE}, pages = {60--69}, year = {1992}, annote = {The best swap data structure is used to find the $k$ smallest spanning trees in time $O(m\log\beta(m,n)+kn^{1/2}\log(m/n))$.}, abstract = {The authors provide data structures that maintain a graph as edges are inserted and deleted, and keep track of the following properties: minimum spanning forests, best swap, graph connectivity, and graph 2-edge-connectivity, in time O(n/sup 1/2/log(m/n)) per change; 3-edge-connectivity, in time O(n/sup 2/3/) per change; 4-edge-connectivity, in time O(n alpha (n)) per change; k-edge-connectivity, in time O(n log n) per change; bipartiteness, 2-vertex-connectivity, and 3-vertex-connectivity, in time O(n log(m/n)) per change; and 4-vertex-connectivity, in time O(n log(m/n)+n alpha (n)) per change. Further results speed up the insertion times to match the bounds of known partially dynamic algorithms. The algorithms are based on a technique that transforms algorithms for sparse graphs into ones that work on any graph, which they call sparsification.}} @techreport{EppGalIta-IBM-93, title = {{Sparsification -- A technique for speeding up dynamic graph algorithms}}, author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Amnon Nissenzweig}, institution = {IBM, T. J. Watson Research Ctr.}, number = {RC 19272 (83907)}, year = {1993}} @article{EppGalIta-JACM-97, title = {{Sparsification -- A technique for speeding up dynamic graph algorithms}}, author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Amnon Nissenzweig}, journal = {J. Assoc. Comput. Mach.}, publisher = {ACM}, volume = {44}, number = {5}, pages = {669--696}, month = {September}, year = {1997}, annote = {This paper combines the FOCS '92 conference version \cite{EppGalIta-FOCS-92} with the ``Improved Sparsification'' tech. report \cite{EppGalIta-TR-93}. It includes a ``best swap'' data structure which is used to find the $k$ smallest spanning trees in time $O(M+kn^{1/2})$ (where $M$ denotes the time to find a single minimum spanning tree in an $m$-edge sparse graph).}} @techreport{EppGalIta-TR-93, title = {{Improved sparsification}}, author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano}, institution = {Univ. of California, Irvine, Dept. Information and Computer Science}, number = {93-20}, year = {1993}, url = {http://www.ics.uci.edu:80/TR/UCI:ICS-TR-93-20}, annote = {The best swap data structure is used to find the $k$ smallest spanning trees in time $O(m\log\log^*m+k\min(n,k)^{1/2})$.}, abstract = {In previous work we introduced {\em sparsification}, a technique that transforms fully dynamic algorithms for sparse graphs into ones that work on any graph, with a logarithmic increase in complexity. In this work we describe an improvement on this technique that avoids the logarithmic