返回Google圖書搜尋

Nested Traveling Salesperson Problem

出版	Lehigh University, 2007
ISBN	05492792379780549279235
URL	http://books.google.com.hk/books?id=SoiTswEACAAJ&hl=&source=gbs_api

註釋This thesis considers the nested traveling salesperson problem on threshold graphs. Given a complete graph, Kn with weights w1, w2, and w 3 assigned to the edges such that the graph induced by the w1edges and the graph induced by the w 1and w2 edges are both threshold graphs we give an efficient algorithm for finding a Hamiltonian path in Kn that maximizes the number of w 1edges and subject to that maximizes the number of w 2 edges. In solving this problem we also solve two general problems on threshold graphs. The first problem characterizes what vertices of a threshold graph can be isolated in a maximum linear forest and which vertices can be ends of paths in a maximum linear forest. The second problem gives necessary and sufficient conditions for a threshold graph along with a matching of some of the vertices, which may or may not be part of the threshold graph, to have a Hamiltonian path that contains the matching.