作者:Geir Dahl、Bj�rnar Realfsen                                    
                                    
                                        DOI:10.1002/1097-0037(200008)36:1<1::aid-net1>3.0.co;2-b
                                    
                                    
                                        日期:2000.8
                                    
                                    We study the cardinality-constrained shortest path problem in acyclic graphs and, in particular, in the class of 2-graphs where we show that the problem may be solved by linear programming. A combinatorial algorithm is introduced based on some adjacency results for associated polytopes. An application in curve approximation is discussed and computational results are given where the mentioned algorithms are compared to Lagrangian relaxation and dynamic programming algorithms. (C) 2000 John Wiley & Sons, Inc.