共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
Zbigniew R. Bogdanowicz 《Discrete Mathematics》2009,309(10):3074-3082
We show that for positive integers n, m with n(n−1)/2≥m≥n−1, the graph Ln,m having n vertices and m edges that consists of an (n−k)-clique and k−1 vertices of degree 1 has the fewest spanning trees among all connected graphs on n vertices and m edges. This proves Boesch’s conjecture [F.T. Boesch, A. Satyanarayana, C.L. Suffel, Least reliable networks and reliability domination, IEEE Trans. Commun. 38 (1990) 2004-2009]. 相似文献
3.
4.
5.
A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively. 相似文献
6.
A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)2) whenO(n
2.81/logn) processors are used. 相似文献
7.
José Elias Claudio Arroyo Pedro Sampaio Vieira Dalessandro Soares Vianna 《Annals of Operations Research》2008,159(1):125-133
This paper proposes a GRASP (Greedy Randomized Adaptive Search Procedure) algorithm for the multi-criteria minimum spanning
tree problem, which is NP-hard. In this problem a vector of costs is defined for each edge of the graph and the problem is
to find all Pareto optimal or efficient spanning trees (solutions). The algorithm is based on the optimization of different
weighted utility functions. In each iteration, a weight vector is defined and a solution is built using a greedy randomized
constructive procedure. The found solution is submitted to a local search trying to improve the value of the weighted utility
function. We use a drop-and-add neighborhood where the spanning trees are represented by Prufer numbers. In order to find a variety of efficient solutions,
we use different weight vectors, which are distributed uniformly on the Pareto frontier.
The proposed algorithm is tested on problems with r=2 and 3 criteria. For non-complete graphs with n=10, 20 and 30 nodes, the performance of the algorithm is tested against a complete enumeration. For complete graphs with
n=20, 30 and 50 nodes the performance of the algorithm is tested using two types of weighted utility functions. The algorithm
is also compared with the multi-criteria version of the Kruskal’s algorithm, which generates supported efficient solutions.
This work was funded by the Municipal Town Hall of Campos dos Goytacazes city. The used computer was acquired with resource
of CNPq. 相似文献
8.
9.
Lionel Levine 《Journal of Combinatorial Theory, Series A》2011,118(2):350-364
We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph G and its directed line graph LG. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case when G is regular of degree k, we show that the sandpile group of G is isomorphic to the quotient of the sandpile group of LG by its k-torsion subgroup. As a corollary we compute the sandpile groups of two families of graphs widely studied in computer science, the de Bruijn graphs and Kautz graphs. 相似文献
10.
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. 相似文献
11.
Yi-Kuei Lin 《Mathematical and Computer Modelling》2002,35(13):1149-1458
Spanning tree enumeration in undirected graphs is an important issue and task in many problems encountered in computer network and circuit analysis. This paper discusses the spanning tree with flow for the case that there are flow requirements between each node pair. An algorithm based on minimal paths (MPs) is proposed to generate all spanning trees without flow. The proposed algorithm is a structured approach, which splits the system into structural MPs first, and also all steps in it are easy to follow. 相似文献
12.
As the extension of the previous work by Ciucu and the present authors [M. Ciucu, W.G. Yan, F.J. Zhang, The number of spanning trees of plane graphs with reflective symmetry, J. Combin. Theory Ser. A 112 (2005) 105-116], this paper considers the problem of enumeration of spanning trees of weighted graphs with an involution which allows fixed points. We show that if G is a weighted graph with an involution, then the sum of weights of spanning trees of G can be expressed in terms of the product of the sums of weights of spanning trees of two weighted graphs with a smaller size determined by the involution of G. As applications, we enumerate spanning trees of the almost-complete bipartite graph, the almost-complete graph, the Möbius ladder, and the almost-join of two copies of a graph. 相似文献
13.
14.
Let G be an undirected graph with nonnegative edge lengths. Given two vertices as sources and all vertices as destinations, we investigated the problem how to construct a spanning tree of G such that the sum of distances from sources to destinations is minimum. In the paper, we show the NP-hardness of the problem and present a polynomial time approximation scheme. For any >0, the approximation scheme finds a (1+)-approximation solution in O(n1/+1) time. We also generalize the approximation algorithm to the weighted case for distances that form a metric space. 相似文献
15.
《Operations Research Letters》2023,51(1):67-71
Let us consider a network flow respecting arc capacities and flow conservation constraints. The flow degree of a node is sum of the flow entering and leaving it. We study the problem of determining a flow that minimizes the maximum flow degree of a node. We show how to solve it in strongly polynomial time with linear programming. 相似文献
16.
17.
18.
In this paper, we review recent work on the minimum labeling spanning tree problem and obtain a new worst-case ratio for the MVCA heuristic. We also present a family of graphs in which the worst-case ratio can be attained. This implies that the new ratio cannot be improved any further. 相似文献
19.
A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem 总被引:1,自引:0,他引:1
We propose a fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. First, an exact pseudo-polynomial algorithm is developed based on a two-variable extension of the well-known matrix-tree theorem. The scaling and approximate binary search techniques are then utilized to yield a fully polynomial approximation scheme. 相似文献
20.
系列平行图上带时间约束的Steiner最小树问题 总被引:1,自引:0,他引:1
陈光亭 《高校应用数学学报(A辑)》2008,23(1):30-34
对一类特殊系列平行图上带有时间约束的Steiner最小树问题,证明了其复杂性为NPC,并给出了一个完全多项式时间近似方案. 相似文献