类 型
18 篇文献
 
Collective Tree Spanners for Unit Disk Graphs with Applications  
In this paper, we establish a novel balanced separator theorem for Unit Disk Graphs (UDGs), which mimics the well-known Lipton and Tarjan’s planar balanced shortest paths separator theorem. We prove t......
Electronic Notes in Discrete Mathematics  2009
0次引用 0 0
Collective tree spanners and routing in AT-free related graphs (Extended Abstract)  
In this paper we study collective additive tree spanners for families of graphs that either contain or are contained in AT-free graphs. We say that a graph G = (V, E) admits a system of µ collective a......
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, LECTURE NOTES IN COMPUT. SCI. 3353  2004
7次引用 0 0
Collective Tree 1-Spanners for Interval Graphs  
Abstract. In this paper we study the existence of a small set T of spanning trees that collectively “1-span ” an interval graph G. Inparticular, for any pair of vertices u, v we require a tree T ∈T su......
Workshop on Graph-Theoretic Concepts in Computer Science  2005
4次引用 0 0
Collective Tree Spanners in Graphs with Bounded Parameters  
In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-w......
4次引用 0 0
Collective Tree Spanners and Routing in AT-free Related Graphs  
In this paper we study collective additive tree spanners for families of graphs that either contain or are contained in AT-free graphs. We say that a graph G = (V,E) admits a system of µ collective ad......
Workshop on Graph-Theoretic Concepts in Computer Science  2004
7次引用 0 0
A New Optimality Measure for Distance Dominating Sets  
Abstract We study the problem of finding the smallest power of an input graph that has k disjoint dominating sets, where the ith power of an input graph G is constructed by adding edges between pairs ......
1次引用 0 0
Spanners for bounded tree-length graphs  
This paper concerns construction of additive stretched spanners with few edges for n-vertex graphs having a tree-decomposition into bags of diameter at most δ, i.e., the tree-length δ graphs. For such......
Theoretical Computer Science  2007
6次引用 0 0
Additive Spanners for Circle Graphs and Polygonal Graphs  
A graph G =(V, E) is said to admit a system of μ collective additive tree r-spanners if there is a system T (G) of at most μ spanning trees of G such that for any two vertices u, v of G a spanning tre......
Workshop on Graph-Theoretic Concepts in Computer Science  2008
0次引用 0 0
Compact Routing Schemes for Bounded Tree-Length Graphs and for k-Chordal Graphs  
In this paper we show how to use the notion of layering-tree introduced in [5], in order to construct efficient routing schemes. We obtain a routing scheme polynomial time constructible for tree-lengt......
Workshop on Distributed Algorithms/International Symposium on Distributed Computing  2004
4次引用 0 0
Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs  
Abstract. In this paper, we propose a new compact and low delay routing labeling scheme for Unit Disk Graphs (UDGs) which often model wireless ad hoc networks. We show that one can assign each vertex ......
Workshop on Algorithms and Data Structures  2009
1次引用 0 0

1/2 第一页 上一页 1 2 下一页
Feedback
Feedback
Feedback
我想反馈:
排行榜