共查询到20条相似文献,搜索用时 0 毫秒
1.
New upper bounds on feedback vertex numbers in butterflies 总被引:1,自引:0,他引:1
Butterflies are undirected graphs of bounded degree. They are widely used as interconnection networks. In this paper we study the feedback vertex set problem for butterflies. We show that the feedback vertex set found by Luccio's algorithm [Inform. Process. Lett. 66 (1998) 59–64] for the k-dimensional butterfly Bk is of size
. Besides, we propose an algorithm to find a feedback vertex set of size either
or
for Bk depending on whether k is even or odd. 相似文献
2.
3.
Chao-Wen Huang 《Theoretical computer science》2011,412(50):6938-6947
In this paper, we investigate the fault-tolerant edge-bipancyclicity of an n-dimensional star graph Sn. Given a set F comprised of faulty vertices and/or edges in Sn with |F|≤n−3 and any fault-free edge e in Sn−F, we show that there exist cycles of every even length from 6 to n!−2|Fv| in Sn−F containing e, where n≥3. Our result is optimal because the star graph is both bipartite and regular with the common degree n−1. The length of the longest fault-free cycle in the bipartite Sn is n!−2|Fv| in the worst case, where all faulty vertices are in the same partite set. We also provide some sufficient conditions from which longer cycles with length from n!−2|Fv|+2 to n!−2|Fv| can be embedded. 相似文献
4.
5.
For a rotator graph with n! nodes, Hsu and Lin [C.C. Hsu, H.R. Lin, H.C. Chang, K.K. Lin, Feedback Vertex Sets in Rotator Graphs, in: Lecture Notes in Comput. Sci., vol. 3984, 2006, pp. 158-164] first proposed an algorithm which constructed a feedback vertex set (FVS) with time complexity O(nn−3). In addition, they found that the size of the FVS is n!/3, which was proved to be minimum. In this paper, we present an efficient algorithm which constructs an FVS for a rotator graph in O(n!) time and also obtains the minimum FVS size n!/3. In other words, this algorithm derives the optimal result with linear time complexity in terms of the number of nodes in the rotator graph. 相似文献
6.
We present algorithmic lower bounds on the size sd of the largest independent sets of vertices in random d-regular graphs, for each fixed d≥3. For instance, for d=3 we prove that, for graphs on n vertices, sd≥0.43475n with probability approaching one as n tends to infinity. 相似文献
7.
Fanica Gavril 《Information Processing Letters》2008,107(1):1-6
We describe a polynomial time algorithm to find a minimum weight feedback vertex set, or equivalently, a maximum weight induced forest, in a circle graph. The circle graphs are the overlap graphs of intervals on a line. 相似文献
8.
In this paper, the diagnosability of n-dimensional star graph Sn under the comparison diagnosis model has been studied. It is proved that Sn is (n−1)-diagnosable under the comparison diagnosis model when n?4. 相似文献
9.
Adnan Mohamed 《Information Processing Letters》2008,106(3):127-131
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. 相似文献
10.
《Information Processing Letters》2014,114(10):568-572
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. 相似文献
11.
Eddie Cheng 《Information Sciences》2007,177(22):4877-4882
We prove that when linearly many vertices are deleted in a Cayley graph generated by a transposition tree, the resulting graph has a large connected component containing almost all remaining vertices. 相似文献
12.
There is a particular family of trivalent vertex-transitive graphs that have been called generalized honeycomb tori by some and brick products by others. They have been studied as hexagonal embeddings on the torus as well. We show that all these graphs are Cayley graphs on generalized dihedral groups. 相似文献
13.
Shahram Latifi 《Information Processing Letters》2007,102(5):196-200
The bounds on f(n,k), the number of faulty nodes to make every (n−k)-dimensional substar Sn−k in an n-dimensional star network Sn, have been derived. The exact value for f(n,k) is determined when n is prime and k=2, or when n−2?k?n. For 2<k<n−2, a general method is presented to derive a set of faulty nodes which damage all Sn−k's in Sn. 相似文献
14.
Let G be a graph. Then T ⊆ V(G) is called an Rk-vertex-cut if G − T is disconnected and each vertex in V(G) − T has at least k neighbors in G − T. The size of a smallest Rk-vertex-cut is the Rk-vertex-connectivity of G and is denoted by κk(G). In this paper, we determine the numbers κ1 and κ2 for Cayley graphs generated by 2-trees, including the popular alternating group graphs. 相似文献
15.
Akka Zemmari 《Information Processing Letters》2008,108(3):119-123
In [Y. Métivier, N. Saheb, A. Zemmari, Analysis of a randomized rendezvous algorithm, Inform. and Comput. 184 (2003) 109-128], the authors introduce and analyze a randomized procedure to implement handshakes in graphs. In this paper, we investigate the same problem in random graphs. We prove results on the probability of success and we study the distribution of the random variable which counts the number of handshakes in the graph. 相似文献
16.
Given a graph G, the problem is to construct a smallest subset S of vertices whose deletion results in an acyclic subgraph. The set S is called a minimum feedback vertex set for G.Tight upper and lower bounds on the cardinality of minimum feedback vertex sets have been previously obtained for some hypercube-like networks, such as meshes, tori, butterflies, cube-connected cycles and hypercubes. In this paper we construct minimum feedback vertex sets and determine their cardinalities in certain shuffle-based interconnection networks, such as shuffle-exchange, de Bruijn and Kautz networks. 相似文献
17.
M. Becker W. Degenhardt J. Doenhardt S. Hertel G. Kaninke W. Keber K. Mehlhorn S. Näher H. Rohnert T. Winter 《Information Processing Letters》1982,15(3):135-136
A probabilistic algorithm is presented which computes the vertex connectivity of an undirected graph G = (V,E) in expected time with error probability at most e provided that |E|<frcase|1/2d|V|2 for some universal constant d<1. 相似文献
18.
In this paper, we study the existence of cycles of all lengths in the recursive circulant graphs, and we show a necessary and sufficient condition for the graph being pancyclic and bipancyclic. 相似文献
19.
The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this paper we find this number and classify all optimal sets for the arrangement graphs, one of the most popular interconnection networks. 相似文献
20.
A box graph is the intersection graph of orthogonal rectangles in the plane. We show that maximum independent set and minimum vertex cover on box graphs can be solved in subexponential time, more precisely, in time , by applying Miller's simple cycle planar separator theorem [J. Comput. System Sci. 32 (1986) 265-279] (in spite of the fact that the input box graph might be strongly non-planar). 相似文献