共查询到20条相似文献,搜索用时 31 毫秒
1.
Lutz Volkmann 《Information Processing Letters》2007,103(6):234-239
Since interconnection networks are often modeled by graphs or digraphs, the edge-connectivity of a graph or arc-connectivity of a digraph are important measurements for fault tolerance of networks.The restricted edge-connectivity λ′(G) of a graph G is the minimum cardinality over all edge-cuts S in a graph G such that there are no isolated vertices in G−S. A connected graph G is called λ′-connected, if λ′(G) exists.In 1988, Esfahanian and Hakimi [A.H. Esfahanian, S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988), 195-199] have shown that each connected graph G of order n?4, except a star, is λ′-connected and satisfies λ′(G)?ξ(G), where ξ(G) is the minimum edge-degree of G.If D is a strongly connected digraph, then we call in this paper an arc set S a restricted arc-cut of D if D−S has a non-trivial strong component D1 such that D−V(D1) contains an arc. The restricted arc-connectivity λ′(D) is the minimum cardinality over all restricted arc-cuts S.We observe that the recognition problem, whether λ′(D) exists for a strongly connected digraph D is solvable in polynomial time. Furthermore, we present some analogous results to the above mentioned theorem of Esfahanian and Hakimi for digraphs, and we show that this theorem follows easily from one of our results. 相似文献
2.
Let G=(V,A) be a digraph. A set T of vertices of G is a twin dominating set of G if for every vertex v∈V?T, there exist u,w∈T (possibly u=w) such that arcs (u,v),(v,w)∈A. The twin domination numberγ∗(G) of G is the cardinality of a minimum twin dominating set of G. In this paper we investigate the twin domination number in generalized de Bruijn digraphs GB(n,d). For the digraphs GB(n,d), we first establish sharp bounds on the twin domination number. Secondly, we give the exact values of the twin domination number for several types of GB(n,d) by constructing minimum twin dominating sets in the digraphs. Finally, we present sharp upper bounds for some special generalized de Bruijn digraphs. 相似文献
3.
Mathieu Liedloff 《Information Processing Letters》2008,107(5):154-157
Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O∗(2n−z), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O∗(2n/2). Another implication is an algorithm for general graphs whose running time is O(n1.7088). 相似文献
4.
A vertex subset F is a k-restricted vertex-cut of a connected graph G if G−F is disconnected and every vertex in G−F has at least k good neighbors in G−F. The cardinality of the minimum k-restricted vertex-cut of G is the k-restricted connectivity of G, denoted by κk(G). This parameter measures a kind of conditional fault tolerance of networks. In this paper, we show that for the n-dimensional alternating group graph AGn, κ2(AG4)=4 and κ2(AGn)=6n−18 for n?5. 相似文献
5.
We propose four fast synchronous distributed message-based algorithms, to identify maximum cardinality sets of edge- and node-disjoint paths, between a source node and a target node in a digraph. Previously, Dinneen et?al. presented two algorithms, based on the classical distributed depth-first search (DFS), which run in O(mf) steps, where m is the number of edges and f is the number of disjoint paths. Combining Cidon??s distributed DFS and our new result, Theorem 3, we propose two improved DFS-based algorithms, which run in O(nf) steps, where n is the number of nodes. We also present improved versions of our two breadth-first search (BFS) based algorithms, with the same complexity upperbound, O(nf). Empirically, for a large set of randomly generated digraphs, our DFS-based edge-disjoint algorithm is 39?% faster than Dinneen et?al.??s edge-disjoint algorithm and our BFS-based edge-disjoint algorithm is 80?% faster. All these improved algorithms have been inspired and guided by a P system modelling exercise, but are suitable for any distributed implementation. 相似文献
6.
《Journal of Parallel and Distributed Computing》1996,32(1):66-73
LetG(V,E) be a simple undirected graph with a maximum vertex degree Δ(G) (or Δ for short), |V| =nand |E| =m. An edge-coloring ofGis an assignment to each edge inGa color such that all edges sharing a common vertex have different colors. The minimum number of colors needed is denoted by χ′(G) (called thechromatic index). For a simple graphG, it is known that Δ ≤ χ′(G) ≤ Δ + 1. This paper studies two edge-coloring problems. The first problem is to perform edge-coloring for an existing edge-colored graphGwith Δ + 1 colors stemming from the addition of a new vertex intoG. The proposed parallel algorithm for this problem runs inO(Δ3/2log3Δ + Δ logn) time usingO(max{nΔ, Δ3}) processors. The second problem is to color the edges of a given uncolored graphGwith Δ + 1 colors. For this problem, our first parallel algorithm requiresO(Δ5.5log3Δ logn+ Δ5log4n) time andO(max{n2Δ,nΔ3}) processors, which is a slight improvement on the algorithm by H. J. Karloff and D. B. Shmoys [J. Algorithms8 (1987), 39–52]. Their algorithm costsO(Δ6log4n) time andO(n2Δ) processors if we use the fastest known algorithm for finding maximal independent sets by M. Goldberg and T. Spencer [SIAM J. Discrete Math.2 (1989), 322–328]. Our second algorithm requiresO(Δ4.5log3Δ logn+ Δ4log4n) time andO(max{n2,nΔ3}) processors. Finally, we present our third algorithm by incorporating the second algorithm as a subroutine. This algorithm requiresO(Δ3.5log3Δ logn+ Δ3log4n) time andO(max{n2log Δ,nΔ3}) processors, which improves, by anO(Δ2.5) factor in time, on Karloff and Shmoys' algorithm. All of these algorithms run in the COMMON CRCW PRAM model. 相似文献
7.
We present a distributed algorithm for maximum cardinality matching in general graphs. On a general graph withn vertices, our algorithm requiresO(n 5/2) messages in the worst case. On trees, our algorithm computes a maximum matching usingO(n) messages after the election of a leader. 相似文献
8.
The generalized de Bruijn digraph GB(n,d) has good properties as an interconnection network topology. The resource location problem in an interconnection network is one of the facility location problems. Finding absorbants of a digraph corresponds to solving a kind of resource location problem. In this paper, we establish bounds on the absorbant number for GB(n,d), and we give some sufficient conditions for the absorbant number of GB(n,d) to achieve the bounds. When d divides n, the extremal digraphs achieving the upper bound are characterized by determining their absorbants. 相似文献
9.
Improving the running time of embedded upward planarity testing 总被引:1,自引:0,他引:1
Sarmad Abbasi 《Information Processing Letters》2010,110(7):274-278
We consider the standard algorithm by Bertolazzi et al. to test the upward planarity of embedded digraphs. We show how to improve its running time from O(n+r2) to , where r is the number of sources and sinks in the digraph. We also discuss an application of this technique: improving the running time of getting a quasi-upward planar drawing for an embedded digraph with minimum number of bends. 相似文献
10.
《Journal of Parallel and Distributed Computing》1998,55(1):94-108
In this paper we describe a parallel algorithm that, given annvertex cubic graphGas input, outputs an orthogonal drawing ofGwithO(n) bends,O(n) maximum edge length, andO(n2) area inO(log n) time using a CRCW PRAM withnprocessors. We give two slight variants of the algorithm. The first generates a drawing in which each edge has at most 2 bends; the total number of bends and the area are bounded byn+3 and [formula], respectively. The second optimizes the number of bends per edge (at most one) even if the values of the other functions are slightly worst. Despite its nonoptimality, this parallel algorithm is the first dealing with nonplanar, nonbiconnected graphs. Moreover, no embedding of the graph is requested as input nor is anst-numbering (orlmc-numbering) computed. 相似文献
11.
Doron Nussbaum Shuye Pu J?rg-Rüdiger Sack Takeaki Uno Hamid Zarrabi-Zadeh 《Algorithmica》2012,64(2):311-325
A bipartite graph G=(A,B,E) is convex on B if there exists an ordering of the vertices of B such that for any vertex v??A, vertices adjacent to v are consecutive in?B. A complete bipartite subgraph of a graph G is called a biclique of G. Motivated by an application to analyzing DNA microarray data, we study the problem of finding maximum edge bicliques in convex bipartite graphs. Given a bipartite graph G=(A,B,E) which is convex on B, we present a new algorithm that computes a maximum edge biclique of G in O(nlog?3 nlog?log?n) time and O(n) space, where n=|A|. This improves the current O(n 2) time bound available for the problem. We also show that for two special subclasses of convex bipartite graphs, namely for biconvex graphs and bipartite permutation graphs, a maximum edge biclique can be computed in O(n??(n)) and O(n) time, respectively, where n=min?(|A|,|B|) and ??(n) is the slowly growing inverse of the Ackermann function. 相似文献
12.
《Journal of Parallel and Distributed Computing》1994,22(1):26-36
The class of cographs, or complement-reducible graphs, arises naturally in many different areas of applied mathematics and computer science. We show that the problem of finding a maximum matching in a cograph can be solved optimally in parallel by reducing it to parenthesis matching. With an n-vertex cograph G represented by its parse tree as input, our algorithm finds a maximum matching in G in O(log n) time using O(n/log n) processors in the EREW-PRAM model. 相似文献
13.
In this paper we consider the problem of finding aclosed partition in a directed graph. This problem has applications in concurrent probabilistic program verification. The best sequential algorithm known for this problem runs inO(mn) time wherem is the number of directed edges andn is the number of vertices in the given digraph. In this paper we present a linear-time sequential algorithm to solve the closed partition problem for planar digraphs that arecompact. We then build on this algorithm to obtain an O(n1.5)-time sequential algorithm to solve the closed partition problem for a general planar digraph.This work was supported in part by NSF Grant CCR 89-10707. 相似文献
14.
Toru Araki 《Information Processing Letters》2007,104(3):86-90
In a digraph G, a vertex u is said to dominate itself and vertices v such that (u,v) is an arc of G. For a positive integer k, a k-tuple dominating set D of a digraph is a subset of vertices such that every vertex is dominated by at least k vertices in D. The k-tuple domination number of a given digraph is the minimum cardinality of a k-tuple dominating set of the digraph. In this letter, we give the exact values of the k-tuple domination number of de Bruijn and Kautz digraphs. 相似文献
15.
《Journal of Symbolic Computation》1994,17(6):513-528
A new random base change algorithm is presented for a permutation group G acting on n points whose worst case asymptotic running time is better for groups with a small to moderate size base than any known deterministic algorithm. To achieve this time bound, the algorithm requires a random generator Rand(G) producing a random element of G with the uniform distribution and so that the time for each call to Rand (G) is bounded by some function f(n, G). The random base change algorithm has probability 1 - 1/|G| of completing in time O(f(n, G) log |G|) and outputting a data structure for representing the point stabilizer sequence relative to the new ordering. The algorithm requires O(n log |G|) space and the data structure produced can be used to test group membership in time O(n log |G|). Since the output of this algorithm is a data structure allowing generation of random group elements in time O(n log |G|), repeated application of the random base change algorithms for different orderings of the permutation domain of G will always run in time O (n log2 |G|). An earlier version of this work appeared in Cooperman and Finkelstein (1992b). 相似文献
16.
《Computers & Mathematics with Applications》2006,51(6-7):1137-1147
In this paper, we consider the bondage number b(G) for a digraph G, which is defined as the minimum number of edges whose removal results in a new digraph with larger domination number. This parameter measures to some extent the robustness of an interconnection network with respect to link failures. By constructing a family of minimum dominating sets, we compute the bondage numbers of the extended de Bruijn digraph and the extended Kautz digraph. As special cases, we obtain for the de Bruijn digraph B(d, n) and the Kautz digraph K(d, n) that b(B(d, n)) = d if n is odd and d ⩽ b(B(d, n)) < 2d if n is even, and b(K(d, n)) = d + 1. 相似文献
17.
An optimal algorithm for the maximum-density path in a tree 总被引:1,自引:0,他引:1
Bang Ye Wu 《Information Processing Letters》2009,109(17):975-979
We studied the problem of finding the maximum-density path in a tree. By spine decomposition and a linear-time algorithm for the maximum density segment problem, we developed an O(nlogn) time algorithm, which improves the previously best result of O(nlog2n) by using centroid decomposition. We also show the time complexity is optimal in the algebraic computation tree model. 相似文献
18.
Let G be a simple and undirected graph. By mi(G) we denote the number of maximal independent sets in G. Erd?s and Moser posed the problem to determine the maximum cardinality of mi(G) among all graphs of order n and to characterize the corresponding extremal graphs attaining this maximum cardinality. The above problem has been solved by Moon and Moser in [J.W. Moon, L. Moser, On cliques in graphs, Israel J. Math. 3 (1965) 23-28]. More recently, Jin and Li [Z. Jin, X. Li, Graphs with the second largest number of maximal independent sets, Discrete Mathematics 308 (2008) 5864-5870] investigated the second largest cardinality of mi(G) among all graphs of order n and characterized the extremal graph attaining this value of mi(G). In this paper, we shall determine the third largest cardinality of mi(G) among all graphs G of order n. Additionally, graphs achieving this value are also determined. 相似文献
19.
We present a distributed algorithm for maximum cardinality matching in general graphs. On a general graph withn vertices, our algorithm requiresO(n
5/2) messages in the worst case. On trees, our algorithm computes a maximum matching usingO(n) messages after the election of a leader.Work on this paper has been supported by the Office of Naval Research under Contract N00014-85-K-0570. 相似文献
20.
C.R. Subramanian 《Information Processing Letters》2006,99(6):227-229
An acyclic edge colouring of a graph is a proper edge colouring in which the union of any two colour classes does not contain a cycle, that is, forms a forest. It is known that there exists such a colouring using at most 16Δ(G) colours where Δ(G) denotes the maximum degree of a graph G. However, no non-trivial constructive bound (which works for all graphs) is known except for the straightforward distance 2 colouring which requires Δ2 colours. We analyse a simple O(mnΔ22(logΔ)) time greedy heuristic and show that it uses at most 5Δ(logΔ+2) colours on any graph. 相似文献