共查询到20条相似文献,搜索用时 0 毫秒
1.
P. Horak 《Discrete Mathematics》2008,308(19):4414-4418
The purpose of this paper is to initiate study of the following problem: Let G be a graph, and k?1. Determine the minimum number s of trees T1,…,Ts, Δ(Ti)?k,i=1,…,s, covering all vertices of G. We conjecture: Let G be a connected graph, and k?2. Then the vertices of G can be covered by edge-disjoint trees of maximum degree ?k. As a support for the conjecture we prove the statement for some values of δ and k. 相似文献
2.
Kth最短路径的Bellman改进算法 总被引:1,自引:1,他引:0
基于对Bellm an算法的改进,得到了求解k th最短路的新算法.改进算法的优势在于从Bellm an算法只能解决最短路问题拓展到求解k th最短路问题,而且可以考虑权重为负数的情况.与传统算法相比,新算法更易于理解. 相似文献
3.
Rachelle R. Bouchat Huy Tài Hà Augustine O?Keefe 《Journal of Combinatorial Theory, Series A》2011,118(8):2411-2425
Let Γ be a rooted (and directed) tree, and let t be a positive integer. The path ideal It(Γ) is generated by monomials that correspond to directed paths of length (t−1) in Γ. In this paper, we study algebraic properties and invariants of It(Γ). We give a recursive formula to compute the graded Betti numbers of It(Γ) in terms of path ideals of subtrees. We also give a general bound for the regularity, explicitly compute the linear strand, and investigate when It(Γ) has a linear resolution. 相似文献
4.
5.
6.
Ryuzo Torii 《Discrete Mathematics》2008,308(17):3782-3804
Path transferability of a graph is a notion that arises from the movement of a path along the graph, the behavior of the path seems as a train on a railroad. In this paper, we introduce two graph notions, transferability and reversibility, and study their properties. 相似文献
7.
We consider the 2-Way Multi Modal Shortest Path Problem (2WMMSPP). Its goal is to find two multi modal paths with total minimal cost, an outgoing path and a return path. The main difficulty lies in the fact that if a private car or bicycle is used during the outgoing path, it has to be picked up during the return path. The shortest return path is typically not equal to the shortest outgoing path as traffic conditions and timetables of public transportation vary throughout the day. In this paper we propose an efficient algorithm based on bi-directional search and provide experimental results on a realistic multi modal transportation network. 相似文献
8.
The algebraic connectivity of a graph G is the second smallest eigenvalue of its Laplacian matrix. Let ■n be the set of all trees of order n. In this paper, we will provide the ordering of trees in ■n up to the last eight trees according to their smallest algebraic connectivities when n ≥ 13. This extends the result of Shao et al. [The ordering of trees and connected graphs by algebraic connectivity. Linear Algebra Appl., 428, 1421-1438 (2008)]. 相似文献
9.
Miodrag Soki? 《Discrete Mathematics》2011,(6):398
We prove a finitary version of the Halpern–Läuchli Theorem. We also prove partition results about strong subtrees. Both results give estimates on the height of trees. 相似文献
10.
11.
Ryuzo Torii 《Discrete Mathematics》2009,309(8):2392-2397
We consider a path as an ordered sequence of distinct vertices with a head and a tail. Given a path, a transfer-move is to remove the tail and add a vertex at the head. A graph is n-transferable if any path with length n can be transformed into any other such path by a sequence of transfer-moves. We show that, unless it is complete or a cycle, a connected graph is δ-transferable, where δ≥2 is the minimum degree. 相似文献
12.
The concept of balance vertices was first investigated by Reid (1999). For the main result “the balance vertices of a tree consist of a single vertex or two adjacent vertices”, Shan and Kang (2004) and Reid and DePalma (2005) improved the length and technique of the proof. In this paper we further discuss the balance vertices on trees in a generalization context. We do not only provide a simple efficient proof for the relevant result but also develop a linear time algorithm to find the set of balance vertices on the underlying tree. 相似文献
13.
Vojtech Blint 《Discrete Applied Mathematics》2008,156(14):2740-2752
A 1-approximation of connected graph G=(V,E) is a tree T=(V,E′) with the same vertex set such that for every two vertices |dG(u,v)−dT(u,v)|1. A polynomial time algorithm is designed for finding such a tree. 相似文献
14.
Pawel Winter 《BIT Numerical Mathematics》1986,26(1):44-62
Enumeration of spanning trees of an undirected graph is one of the graph problems that has received much attention in the literature. In this paper a new enumeration algorithm based on the idea of contractions of the graph is presented. The worst-case time complexity of the algorithm isO(n+m+nt) wheren is the number of vertices,m the number of edges, andt the number of spanning trees in the graph. The worst-case space complexity of the algorithm isO(n
2). Computational analysis indicates that the algorithm requires less computation time than any other of the previously best-known algorithms. 相似文献
15.
For given graphs G and H, the Ramsey numberR(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper, we investigate the Ramsey number R(∪G,H), where G is a tree and H is a wheel Wm or a complete graph Km. We show that if n?3, then R(kSn,W4)=(k+1)n for k?2, even n and R(kSn,W4)=(k+1)n-1 for k?1 and odd n. We also show that . 相似文献
16.
Pasquale Avella Maurizio Boccia Antonio Sforza 《Journal of Mathematical Modelling and Algorithms》2004,3(1):1-17
In the management and control of a vehicle fleet on a road network, the problem arises of finding the best route in relation
to the mission of the fleet and to the typology of freight or users. Sometimes the route has to be adapted not only to current
traffic conditions, but also to the physical, geometric and functional attributes of the roads, related to their urban location
and environmental characteristics.
This problem is approached here through an extension of the classic Shortest Path problem, named Resource Constrained Shortest
Path problem (RCSP), where the resources are related to the road link attributes, assumed as relevant to the specific planning
problem. A classification scheme of these attributes is first proposed and RCSP is described and reviewed. Next, a General
Resource Constrained Shortest Path problem (GRCSP) is defined, which can be found in all cases where it is necessary to plan,
statically or dynamically, the path of a vehicle and to respect a set of constraints expressed in terms of parameters and
indices associated with the roads on the network. For this general problem a model has been formulated and a Branch and Cut
solution approach is proposed. Computational results obtained on test and real networks during the experimentation of a fleet
with low emission vehicles are also given.
This revised version was published online in August 2006 with corrections to the Cover Date. 相似文献
17.
Given two rooted, labeled trees P and T the tree path subsequence problem is to determine which paths in P are subsequences of which paths in T. Here a path begins at the root and ends at a leaf. In this paper we propose this problem as a useful query primitive for XML data, and provide new algorithms improving the previously best known time and space bounds. 相似文献
18.
The location of path-shaped facilities on trees has been receiving a growing attention in the specialized literature in the recent years. Examples of such facilities include railroad lines, highways and public transit lines. Most of the papers deal with the problem of locating a path on a tree by minimizing either the maximum distance from the vertices of the tree to the facility or of minimizing the sum of the distances from all the vertices of the tree to the path. However, neither of the two above criteria alone capture all essential elements of a location problem. The sum of the distances criterion alone may result in solutions which are unacceptable from the point of view of the service level for the clients who are located far away from the facilities. On the other hand, the criterion of the minimization of the maximum distance, if used alone, may lead to very costly service systems. In the literature, there is just one paper that considers the problem of finding an optimal location of a path on a tree using combinations of the two above criteria, and efficient algorithms are provided. In particular, the cases where one criterion is optimized subject to a restriction on the value of the other are considered and linear time algorithms are presented. However, these problems do not consider any bound on the length or cost of the facility. In this paper we consider the two following problems: find a path which minimizes the sum of the distances such that the maximum distance from the vertices of the tree to the path is bounded by a fixed constant and such that the length of the path is not greater than a fixed value; find a path which minimizes the maximum distance with the sum of the distances being not greater than a fixed value and with bounded length. From an application point of view the constraint on the length of the path may refer to a budget constraint for establishing the facility. The restriction on the length of the path complicates the two problems but for both of them we give O(n log2 n) divide-and-conquer algorithms. 相似文献
19.
We provide a proof of Sholander’s claim [M. Sholander, Trees, lattices, order, and betweenness, Proceedings of the American Mathematical Society 3 (1952) 369–381] concerning the representability of collections of so-called segments by trees, which yields a characterization of the interval function of a tree. Furthermore, we streamline Burigana’s characterization [L. Burigana, Tree representations of betweenness relations defined by intersection and inclusion, Mathematics and Social Sciences 185 (2009) 5–36] of tree betweenness and provide a relatively short proof. 相似文献
20.
Path relinking for the vehicle routing problem 总被引:3,自引:0,他引:3
This paper describes a tabu search heuristic with path relinking for the vehicle routing problem. Tabu search is a local search
method that explores the solution space more thoroughly than other local search based methods by overcoming local optima.
Path relinking is a method to integrate intensification and diversification in the search. It explores paths that connect
previously found elite solutions. Computational results show that tabu search with path relinking is superior to pure tabu
search on the vehicle routing problem. 相似文献