Results 251 to 260 of about 133,936 (292)
Some of the next articles are maybe not open access.
DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
Cybernetics and Systems, 2012A degree-constrained minimum spanning tree (DCMST) problem is an NP-hard combinatorial optimization problem in graph theory seeking the minimum cost spanning tree with the additional constraint on the vertex degree. Several different approaches have been proposed in the literature to solve this problem using a deterministic graph.
Kavita Singh, Shyam Sundar
exaly +4 more sources
Degree constrained minimum spanning tree problem: a learning automata approach
The Journal of Supercomputing, 2013Degree-constrained minimum spanning tree problem is an NP-hard bicriteria combinatorial optimization problem seeking for the minimum weight spanning tree subject to an additional degree constraint on graph vertices. Due to the NP-hardness of the problem, heuristics are more promising approaches to find a near optimal solution in a reasonable time. This
Javad Akbari Torkestani
openaire +3 more sources
Average distance, minimum degree, and spanning trees
Journal of Graph Theory, 2000The average distance \(\mu (G)\) of a connected graph is the arithmetic mean of the distances between all pairs of vertices of \(G\); for a survey see the reviewer's paper [J. Graph Theory 8, 1-21 (1984; Zbl 0552.05048 and Zbl 0541.05056)]. The authors prove that every connected graph of order \(n\) and minimum degree \(\delta\) has a spanning tree \(T\
Dankelmann, Peter, Entringer, Roger
openaire +2 more sources
On the maximum degree of minimum spanning trees
Proceedings of the tenth annual symposium on Computational geometry - SCG '94, 1994Motivated by practical VLSI routing applications, we study the maximum vertex degree of a minimum spanning tree (MST). We prove that under the Lp norm, the maximum vertex degree over all MSTs is equal to the Hadwiger number of the corresponding unit ball; we show an even tighter bound for MSTs where the maximum degree is minimized.
Gabriel Robins, Jeffrey S. Salowe
openaire +1 more source
FUZZY RANDOM DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM
International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2007The degree-constrained minimum spanning tree problem (dc-MST) is to find a minimum spanning tree of the given graph, subject to constraints on node degrees. This paper investigates the dc-MST problem with fuzzy random weights. Three concepts are presented: expected fuzzy random dc-MST, (α,β)-dc-MST and the most chance dc-MST according to different ...
WEI LIU, CHENGJING YANG
openaire +1 more source
Minimum Bounded Degree Spanning Trees
2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006We consider the minimum cost spanning tree problem under the restriction that all degrees must be at most a given value k. We show that we can efficiently find a spanning tree of maximum degree at most k+2 whose cost is at most the cost of the optimum spanning tree of maximum degree at most k. This is almost best possible.
openaire +1 more source
RPL load balancing via minimum degree spanning tree
2016 IEEE 12th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), 2016RPL is the routing protocol for low-power and lossy networks and has recently been considered as the standard routing protocol for IPv6 based wireless sensor networks using the IEEE 802.15.4 protocol. RPL is oriented towards supporting multi-point to point communications in which multiple points typically communicate with one sink node that considered ...
Marwa Mamdouh +2 more
openaire +1 more source
Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree
Journal of Heuristics, 2001zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Krishnamoorthy, Mohan +2 more
openaire +2 more sources
The vertex degrees of minimum spanning trees
European Journal of Operational Research, 2000zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +1 more source
An approximate algorithm for degree constraint minimum spanning tree
2010 International Conference on Computer and Communication Technology (ICCCT), 2010DCMST (Degree Constraint Minimum Spanning Tree) is a special case of minimum spanning tree problem which is concerned with finding a spanning tree of a nonnegative edge weighted graph such that all nodes satisfy degree restrictions and total edge length is minimum.
Sweetesh Singh +3 more
openaire +1 more source