Keyword: minimum spanning tree

Found 11 papers in total
Convex partitions with 2‐edge connected dual graphs
Convex partitions with 2‐edge connected dual graphs
2011,
It is shown that for every finite set of disjoint convex polygonal obstacles in the...
Linear Time Algorithms for Generalized Edge Dominating Set Problems
Linear Time Algorithms for Generalized Edge Dominating Set Problems
2008,
We prove that a generalization of the edge dominating set problem, in which each edge...
Finding socially best spanning trees
Finding socially best spanning trees
2011,
This article combines Social Choice Theory with Discrete Optimization. We assume that...
Testing Convexity Properties of Tree Colorings
Testing Convexity Properties of Tree Colorings
2011,
A coloring of a graph is convex if it induces a partition of the vertices into...
k‐Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees
k‐Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees
2011,
Low distortion probabilistic embedding of graphs into approximating trees is an...
On the directed Full Degree Spanning Tree problem
On the directed Full Degree Spanning Tree problem
2011,
We study the parameterized complexity of a directed analog of the Full Degree Spanning...
Cost allocation protocols for supply contract design in network situations
Cost allocation protocols for supply contract design in network situations
2009,
The class of Construct and Charge (CC–) rules for minimum cost spanning tree...
Approximating k-hop minimum-spanning trees
Approximating k-hop minimum-spanning trees
2005,
Given a complete graph on ∼ n nodes with metric edge costs, the minimum-cost k...
Local search for the minimum label spanning tree problem with bounded color classes
Local search for the minimum label spanning tree problem with bounded color classes
2003,
In the Minimum Label Spanning tree problem, the input consists of an edge-colored...
Approximating minimum spanning tree of depth 2
Approximating minimum spanning tree of depth 2
1999,
We prove that the problem of finding, in an undirected graph with non-negative costs...
A heuristic algorithm for the mini-max spanning forest problem
A heuristic algorithm for the mini-max spanning forest problem
1996,
In this paper we formulate the mini-max spanning forest problem for undirected graphs...
Papers per page: