类 型
13 篇文献
 
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
Graphs and Combinatorics © Springer-Verlag 2008 On 2-Detour Subgraphs of the Hypercube  
Abstract. A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x, y ∈ V (G), dH (x, y) ≤ dG(x, y) + 2. We prove a conjecture of Erdős, Hamburger, Pippert, and Weakley by showing......
0次引用 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
On k-detour subgraphs of hypercubes  
A spanning subgraph G of a graph H is a k-detour subgraph of H if for each pair of vertices x, y ∈ V (H), the distance, distG(x, y), between x and y in G exceeds that in H by at most k. Such subgraphs......
Journal of Graph Theory  2008
2次引用 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
On k-Detour Subgraphs of  
Abstract: A spanning subgraph G of a graph H is a k-detour subgraph of H if for each pair of vertices x, y ∈ V(H), the distance, distG(x, y), between x and y in G exceeds that in H by at most k. Such ......
0次引用 0 0
I.: Collective tree spanners of graphs  
Abstract. In this paper we introduce a new notion of collective tree spanners. We say that a graph G =(V,E) admits a system of µ collective additive tree r-spanners if there is a system T (G) of at mo......
Siam Journal on Discrete Mathematics  2006
18次引用 0 0
Network Flow Spanners  
Abstract. In this paper, motivated by applications of ordinary (distance) spanners in communication networks and to address such issues as bandwidth constraints on network links, link failures, networ......
Latin American Theoretical INformatics  2006
1次引用 0 0
Collective Tree Spanners in Graphs with Bounded Genus, Chordality, Tree-Width, or Clique-Width  
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- ......
International Symposium on Algorithms and Computation  2005
2次引用 0 0
On 2-Detour Subgraphs of the Hypercube  
Abstract. A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x,y ∈ V (G), dH(x,y) ≤ dG(x,y) + 2. We prove a conjecture of Erdős, Hamburger, Pippert, and Weakley by showing tha......
Graphs and Combinatorics  2008
0次引用 0 0

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