摘要:

AbstractA truncated‐Newton method is applied to the spatial price equilibrium problem and the method is compared with other specialized techniques that exploit the inherent network structure of the problem. Variants of the linear conjugate gradient algorithm for approximately solving the Newton equations are discussed. Numerical results for the truncated‐Newton method are compared with those of a block‐SOR method. Tests indicate that the two approaches are comparable when transportation costs are linear. A truncated‐Newton algorithm is far superior if the transportation costs are no

ISSN:0028-3045    

DOI:10.1002/net.3230250403

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractAlthough the general problem of subgraph isomorphism is NP‐complete, polynomial‐time algorithms exist for recognizing any fixed subgraph. However, certain subgraphs appear easier to recognize than others. In this paper, we present general algorithms for fixed‐subgraph isomorphism which improve or unify previous results. In particular, we present an O(nfm) algorithm for recognizing a fixed subgraphHwith flower numberfwithin a graphGwithnvertices andmedges. Special cases of this algorithm match the best algorithms known for recognizing small paths, cycles, and cliques. Further, we improve previous results for recognizingC5and small even cyclesC2k

ISSN:0028-3045    

DOI:10.1002/net.3230250404

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractLet

ISSN:0028-3045    

DOI:10.1002/net.3230250405

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractThe task of developing daily schedules for a steel rolling mill has been formulated as a Prize Collecting Traveling Salesman (PCTS) Problem, in which a salesman who gets a prize for every city he visits seeks a minimum‐cost tour including enough cities to collect a required amount of prize money. This paper addresses the facial structure of the PCTS polytope, the convex hull of solutions to the PCTS problem. In an earlier paper, we generalized to the PCTS polytope the subtour elimination inequalities for the Asymmetric Traveling Salesman (ATS) polytope. Here, we give a general method for deriving a facet defining inequality for the PCTS polytope from any facet defining inequality for the ATS polytope. We apply the procedure to several well‐known families of facet inducing inequalities for the ATS polytope: comb, odd CAT, SD, clique tree, and lifted cycle inequalities. We also extend the cloning and clique lifting procedure for the ATS polytope to the PCTS polyt

ISSN:0028-3045    

DOI:10.1002/net.3230250406

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230250402

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY