Design and analysis of the rotational binary graph as an alternative to hypercube and Torus

Network cost is equal to degree?×?diameter and is one of the important measurements when evaluating graphs. Torus and hypercube are very well-known graphs. When these graphs expand, a Torus has an advantage in that its degree does not increase. A hypercube has a shorter diameter than that of other graphs, because when the graph expands, the diameter increases by 1. Hypercube Q_n has 2ⁿ nodes, and its diameter is n. We propose the rotational binary graph (RBG), which has the advantages of both hypercube and Torus. RBG_n has 2ⁿ nodes and a degree of 4. The diameter of RBG_n would be 1.5n?+?1. In this paper, we first examine the topology properties of RBG. Second, we construct a binary spanning tree in RBG. Third, we compare other graphs to RBG considering network cost specifically. Fourth, we suggest a broadcast algorithm with a time complexity of 2n???2. Finally, we prove that RBG_n embedded into hypercube Q_n results in dilation n, and expansion 1, and congestion 7.

     

Optimal Reconstruction of Graphs under the Additive Model

We study the problem of reconstructing unknown graphs under the additive combinatorial search model. The main result concerns the reconstruction of bounded degree graphs, i.e., graphs with the degree of all vertices bounded by a constant d . We show that such graphs can be reconstructed in O(dn) nonadaptive queries, which matches the information-theoretic lower bound. The proof is based on the technique of separating matrices. A central result here is a new upper bound for a general class of separating matrices. As a particular case, we obtain a tight upper bound for the class of d -separating matrices, which settles an open question stated by Lindstr?m in [20]. Finally, we consider several particular classes of graphs. We show how an optimal nonadaptive solution of O(n ² / log n) queries for general graphs can be obtained. We also prove that trees with unbounded vertex degree can be reconstructed in a linear number of queries by a nonadaptive algorithm. Received August 1997; revised January 1999.     

A refined search tree technique for Dominating Set on planar graphs

We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times O(8^kn) and O(8^kk+n³), where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general “annotated” problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.     

Parallel Algorithms for Maximum Matching in Complements of Interval Graphs and Related Problems

Given a set of n intervals representing an interval graph, the problem of finding a maximum matching between pairs of disjoint (nonintersecting) intervals has been considered in the sequential model. In this paper we present parallel algorithms for computing maximum cardinality matchings among pairs of disjoint intervals in interval graphs in the EREW PRAM and hypercube models. For the general case of the problem, our algorithms compute a maximum matching in O( log ³ n) time using O(n/ log ² n) processors on the EREW PRAM and using n processors on the hypercubes. For the case of proper interval graphs, our algorithm runs in O( log n ) time using O(n) processors if the input intervals are not given already sorted and using O(n/ log n ) processors otherwise, on the EREW PRAM. On n -processor hypercubes, our algorithm for the proper interval case takes O( log n log log n ) time for unsorted input and O( log n ) time for sorted input. Our parallel results also lead to optimal sequential algorithms for computing maximum matchings among disjoint intervals. In addition, we present an improved parallel algorithm for maximum matching between overlapping intervals in proper interval graphs. Received November 20, 1995; revised September 3, 1998.     

Space-Efficient Counting in Graphs on Surfaces

We consider the problem of counting the number of spanning trees in planar graphs. We prove tight bounds on the complexity of the problem, both in general and especially in the modular setting. We exhibit the problem to be complete for Logspace when the modulus is 2^k, for constant k. On the other hand, we show that for any other modulus and in the non-modular case, our problem is as hard in the planar case as for the case of arbitrary graphs. The techniques used are algebraic topological that may be useful in many other problems involving planar or higher genus graphs – such as higher genus graph recognition in Logspace. In the spirit of counting problems modulo 2^k, we also exhibit a highly parallel ?L\oplus {\bf L} algorithm for finding the value of a permanent modulo 2^k. Previously, the best known result in this direction was Valiant’s result that this problem lies in P. We also show that we can count the number of perfect matchings modulo 2^k in an arbitrary graph in P. This extends Valiant’s result for the permanent, since the Permanent may be modeled as counting the number of perfect matchings in bipartite graphs.     

The bicube: an interconnection of two hypercubes

We consider two definitions of the even-dimensional hypercube given in the literature. The labelled graphs obtained by two definitions are not same, but one is isomorphic to the other. By interconnecting two labelled graphs in such a way that each pair of vertices with the same label are joined by an edge, we construct a vertex-symmetric graph with the diameter about half that of a comparable hypercube. We extend the result to a general scheme for interconnecting two hypercubes to produce a network topology called the bicube. We show that the bicube preserves the vertex-symmetry, bipartiteness, hamiltonian and bipancyclic properties of the hypercube, and is highly edge-symmetric.     

More Efficient Topological Sort Using Reconfigurable Optical Buses

Topological sort of an acyclic graph has many applications such as job scheduling and network analysis. Due to its importance, it has been tackled on many models. Dekel et al. [3], proposed an algorithm for solving the problem in O(log² N) time on the hypercube or shuffle-exchange networks with O(N ³) processors. Chaudhuri [2], gave an O(log N) algorithm using O(N ³) processors on a CRCW PRAM model. On the LARPBS (Linear Arrays with a Reconfigurable Pipelined Bus System) model, Li et al. [5] showed that the problem for a weighted directed graph with N vertices can be solved in O(log N) time by using N ³ processors. In this paper, a more efficient topological sort algorithm is proposed on the same LARPBS model. We show that the problem can be solved in O(log N) time by using N ³/log N processors. We show that the algorithm has better time and processor complexities than the best algorithm on the hypercube, and has the same time complexity but better processor complexity than the best algorithm on the CRCW PRAM model.     

Maximum Induced Matchings for Chordal Graphs in Linear Time

The Maximum Induced Matching (MIM) Problem asks for a largest set of pairwise vertex-disjoint edges in a graph which are pairwise of distance at least two. It is well-known that the MIM problem is NP-complete even on particular bipartite graphs and on line graphs. On the other hand, it is solvable in polynomial time for various classes of graphs (such as chordal, weakly chordal, interval, circular-arc graphs and others) since the MIM problem on graph G corresponds to the Maximum Independent Set problem on the square G ^*=L(G)² of the line graph L(G) of G, and in some cases, G ^* is in the same graph class; for example, for chordal graphs G, G ^* is chordal. The construction of G ^*, however, requires time, where m is the number of edges in G. Is has been an open problem whether there is a linear-time algorithm for the MIM problem on chordal graphs. We give such an algorithm which is based on perfect elimination order and LexBFS.     

On the induced matching problem

We study extremal questions on induced matchings in certain natural graph classes. We argue that these questions should be asked for twinless graphs, that is graphs not containing two vertices with the same neighborhood. We show that planar twinless graphs always contain an induced matching of size at least n/40 while there are planar twinless graphs that do not contain an induced matching of size (n+10)/27. We derive similar results for outerplanar graphs and graphs of bounded genus. These extremal results can be applied to the area of parameterized computation. For example, we show that the induced matching problem on planar graphs has a kernel of size at most 40k that is computable in linear time; this significantly improves the results of Moser and Sikdar (2007). We also show that we can decide in time O(k⁹¹+n) whether a planar graph contains an induced matching of size at least k.     

Fast Recognition of Fibonacci Cubes

Fibonacci cubes are induced subgraphs of hypercubes based on Fibonacci strings. They were introduced to represent interconnection networks as an alternative to the hypercube networks. We derive a characterization of Fibonacci cubes founded on the concept of resonance graphs. The characterization is the basis for an algorithm which recognizes these graphs in O(mlog n) time. A. Vesel supported by the Ministry of Science of Slovenia under the grant 0101-P-297.     

Counting the Number of Perfect Matchings in K5-Free Graphs

Counting the number of perfect matchings in graphs is a computationally hard problem. However, in the case of planar graphs, and even for K_3,3-free graphs, the number of perfect matchings can be computed efficiently. The technique to achieve this is to compute a Pfaffian orientation of a graph. In the case of K₅-free graphs, this technique will not work because some K₅-free graphs do not have a Pfaffian orientation. We circumvent this problem and show that the number of perfect matchings in K₅-free graphs can be computed in polynomial time. We also parallelize the sequential algorithm and show that the problem is in TC². We remark that our results generalize to graphs without singly-crossing minor.     

Maximum matchings in planar graphs via gaussian elimination

We present a randomized algorithm for finding maximum matchings in planar graphs in timeO(n ^ω/2), whereω is the exponent of the best known matrix multiplication algorithm. Sinceω<2.38, this algorithm breaks through theO(n ^1.5) barrier for the matching problem. This is the first result of this kind for general planar graphs. We also present an algorithm for generating perfect matchings in planar graphs uniformly at random usingO(n ^ω/2) arithmetic operations. Our algorithms are based on the Gaussian elimination approach to maximum matchings introduced in [16]. This research was supported by KBN Grant 4T11C04425.     

Load balancing and routing on the hypercube and related networks

Several results related to the load balancing problem on the hypercube, the shuffle-exchange, the cube-connected cycles, and the butterfly are shown. Implications of these results for routing algorithms are also discussed. Our results include the following:

• Efficient load balancing algorithms are found for the hypercube, the shuffle-exchange, the cube-connected cycles, and the butterfly.

• Load balancing is shown to require more time on a p-processor shuffle-exchange, cube-connected cycle or butterfly than on a p-processor weak hypercube.

• Routing n packets on a p-processor hypercube can be done optimally whenever n = p^1+1/k, for any fixed k > 0.

     

An Efficient Algorithm for Solving Pseudo Clique Enumeration Problem

The problem of finding dense structures in a given graph is quite basic in informatics including data mining and data engineering. Clique is a popular model to represent dense structures, and widely used because of its simplicity and ease in handling. Pseudo cliques are natural extension of cliques which are subgraphs obtained by removing small number of edges from cliques. We here define a pseudo clique by a subgraph such that the ratio of the number of its edges compared to that of the clique with the same number of vertices is no less than a given threshold value. In this paper, we address the problem of enumerating all pseudo cliques for a given graph and a threshold value. We first show that it seems to be difficult to obtain polynomial time algorithms using straightforward divide and conquer approaches. Then, we propose a polynomial time, polynomial delay in precise, algorithm based on reverse search. The time complexity for each pseudo clique is O(Δlog |V|+min {Δ ²,|V|+|E|}). Computational experiments show the efficiency of our algorithm for both randomly generated graphs and practical graphs.     

Routing Permutations on Graphs via Factors

We deal with the permutation routing problem on graphs modeling interconnection networks. In our model, calledrouting via factors, at each routing step, the communication pattern is a directed 1-factor in a symmetric digraph. This adds a new feature, that of continuous packet movement, to preciously studied routing types, where the routing of a permutation is reduced to a sequence of permutations from a given class. We especially focus on bipartite graphs and we give sufficient conditions for a graph to be rearrangeable in our model. We propose a general technic for routing via factors that we apply to the 2D mesh and the hypercube.     

Fast algorithms for bit-serial routing on a hypercube

In this paper we describe anO(logN)-bit-step randomized algorithm for bit-serial message routing on a hypercube. The result is asymptotically optimal, and improves upon the best previously known algorithms by a logarithmic factor. The result also solves the problem of on-line circuit switching in anO(1)-dilated hypercube (i.e., the problem of establishing edge-disjoint paths between the nodes of the dilated hypercube for any one-to-one mapping).Our algorithm is adaptive and we show that this is necessary to achieve the logarithmic speedup. We generalize the Borodin-Hopcroft lower bound on oblivious routing by proving that any randomized oblivious algorithm on a polylogarithmic degree network requires at least (log² N/log logN) bit steps with high probability for almost all permutations.This research was supported by the Defense Advanced Research Projects Agency under Contracts N00014-87-K-825 and N00014-89-J-1988, the Air Force under Contract AFOSR-89-0271, and the Army under Contract DAAL-03-86-K-0171. This work was completed while the third and fourth authors were at the Laboratory for Computer Science, Massachusetts Institute of Technology.     

Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems

A sequence of exact algorithms to solve the Vertex Cover and Maximum Independent Set problems have been proposed in the literature. All these algorithms appeal to a very conservative analysis that considers the size of the search tree, under a worst-case scenario, to derive an upper bound on the running time of the algorithm. In this paper we propose a different approach to analyze the size of the search tree. We use amortized analysis to show how simple algorithms, if analyzed properly, may perform much better than the upper bounds on their running time derived by considering only a worst-case scenario. This approach allows us to present a simple algorithm of running time O(1.194^kk² + n) for the parameterized Vertex Cover problem on degree-3 graphs, and a simple algorithm of running time O(1.1255ⁿ) for the Maximum Independent Set problem on degree-3 graphs. Both algorithms improve the previous best algorithms for the problems.     

Vertex-pancyclicity of twisted cubes with maximal faulty edges

The n-dimensional twisted cube, denoted by TQ _n , a variation of the hypercube, possesses some properties superior to the hypercube. In this paper, we show that every vertex in TQ _n lies on a fault-free cycle of every length from 6 to 2 ⁿ , even if there are up to n?2 link faults. We also show that our result is optimal.