首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 48 毫秒
1.
2.
3.
A path in an edge-colored graph G, whose adjacent edges may have the same color, is called a rainbow path if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the minimum integer i for which there exists an i-edge-coloring of G such that every two distinct vertices of G are connected by a rainbow path. The strong rainbow connection number src(G) of G is the minimum integer i for which there exists an i-edge-coloring of G such that every two distinct vertices u and v of G are connected by a rainbow path of length d(u,v). In this paper, we give upper and lower bounds of the (strong) rainbow connection numbers of Cayley graphs on Abelian groups. Moreover, we determine the (strong) rainbow connection numbers of some special cases.  相似文献   

4.
Pancake graphs have been proposed as an attractive alternative to hypercube networks. They have a smaller diameter and a lower degree. They also have a hierarchical structure which can be exploited in designing algorithms.In this paper, we propose a leader election algorithm for oriented pancake graphs. The algorithm has a message complexity that is linear in the order of the graph.  相似文献   

5.
The longest path problem, that is, finding a simple path with the maximum number of vertices, is a well-known NP-hard problem with many applications. However, for some classes of graphs, including solid grid graphs and grid graphs with some holes, it is open. An L-shaped grid graph is a special kind of a rectangular grid graph with a rectangular hole. In this paper, we show that a longest path between two given vertices s and t of an L-shaped grid graph can be computed in linear time.  相似文献   

6.
k-tuple domination in graphs   总被引:1,自引:0,他引:1  
In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset in a graph such that every vertex in the graph is dominated by at least k vertices in this set. The current paper studies k-tuple domination in graphs from an algorithmic point of view. In particular, we give a linear-time algorithm for the k-tuple domination problem in strongly chordal graphs, which is a subclass of chordal graphs and includes trees, block graphs, interval graphs and directed path graphs. We also prove that the k-tuple domination problem is NP-complete for split graphs (a subclass of chordal graphs) and for bipartite graphs.  相似文献   

7.
The problem of counting maximal independent sets is #P-complete for chordal graphs but solvable in polynomial time for its subclass of interval graphs. This work improves upon both of these results by showing that the problem remains #P-complete when restricted to directed path graphs but that a further restriction to rooted directed path graphs admits a polynomial time solution.  相似文献   

8.
AnOE¦log2 n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n 2)-time andO(n 2)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.  相似文献   

9.
10.
For a set S of n points in convex position in the plane, let P(S) denote the set of all plane spanning paths of S. The geometric path graph of S, denoted by Gn, is the graph with P(S) as its vertex set and two vertices P,QP(S) are adjacent if and only if P and Q can be transformed to each other by means of a single edge replacement. Recently, Akl et al. [S.G. Akl, K. Islam, H. Meijer, On planar path transformation, Inform. Process. Lett. 104 (2007) 59-64] showed that the diameter of Gn is at most 2n−5. In this note, we derive the exact diameter of Gn for n?3.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号