Search

The generalized hypercube is a highly-connective network proposed by Bhuyan and Agrawal. In this paper, we study the restricted connectivity and fault-free unicast algorithm in the generalized hypercube. Firstly, we prove that the restricted connectivity of a r -dimensional generalized hypercube G (m r , m r − 1 , … , m 1) is 2 κ (G) − n , where κ (G) denotes the connectivity of G (m r , m r − 1 , … , m 1) and n = max { m 1 , m 2 , … , m r } , under the condition that each vertex has at least one fault-free neighbor. It is almost twice the traditional connectivity of G (m r , m r − 1 , … , m 1). Furthermore, we present an O (κ (G) 3) fault-free unicast algorithm in the generalized hypercube. [ABSTRACT FROM AUTHOR]

The graph isomorphism problem is to check if two given graphs are isomorphic. Graph isomorphism is a well studied problem and numerous algorithms are available for its solution. In this paper we present algorithms for graph isomorphism that employ the spectra of graphs. An open problem that has fascinated many a scientist is if there exists a polynomial time algorithm for graph isomorphism. Though we do not solve this problem in this paper, the algorithms we present take polynomial time. These algorithms have been tested on a good collection of instances. However, we have not been able to prove that our algorithms will work on all possible instances. In this paper, we also give a new construction for cospectral graphs. [ABSTRACT FROM AUTHOR]

In this paper, we discuss a simple, Monte Carlo algorithm for the problem of checking whether a Quantified Boolean Formula (QBF) in Conjunctive Normal Form (CNF), with at most two literals per clause has a model. The term k-CNF is used to describe boolean formulas in CNF, with at most /c literals per clause and the problem of checking whether a given k-CNF formula is satisfiable is called the k-SAT problem. A QBF is a boolean formula, accompanied by a quantifier string which imposes a linear ordering on the variables of that formula. The problem of finding a model for a QBF formula in CNF, with at at most k literals per clause is called the QkSAT problem. The QkSAT problem is PSPACE-complete, for k ≥ 3. However, the Q2SAT problem can be decided in polynomial time; the graph-based procedure, discussed in [1], is the first such algorithm for this problem. This procedure requires the construction of a global implication graph, corresponding to the input formula and searching for certain paths in this graph. Hence the complete set of clauses must be part of the input. We propose an incremental, randomized approach for the Q2SAT problem that is essentially local in nature, in that the complete clausal set need not be provided at any time, in the presence of a verifier. We show that the randomized algorithm can be analyzed as a one-dimensional random walk, with one reflecting barrier and one absorbing barrier. On a Q2SAT instance with in clauses on n variables, our coin-flipping algorithm runs in time O(n² V(m, n)), where V(m, n) is the time required to verify that a given model satisfies the formula. Additionally, if the instance is satisfiable, the probability that our algorithm fails to find a model is less than one half. The design and analysis of a randomized algorithm for a problem, is important from both the theoretical and the practical perspectives. Randomized approaches tend to be simple and elegant, thereby making the process of checking correctness, effortless as well. The randomized approach discussed in this paper lays the groundwork for analyzing a number of problems related to 2CNF formulas and directed graphs. We remark that our work in this paper is the first randomized algorithm for a class of QBFs. [ABSTRACT FROM AUTHOR]

For a connected non-complete graph, a vertex separator is a subset of vertices whose deletion increases the number of connected components and the vertex connectivity of the graph refers to the size of a minimum vertex separator. A graph with the vertex con-nectivity fc is said to be k-vertex connected. Given a fc-vertex connected graph G, vertex connectivity augmentation determines a smallest set of edges whose augmentation to G makes it (k + l)-vertex connected. In this paper, we report our study on connectiv-ity augmentation in 1-connected graphs, 2-connected graphs, and fc-connected chordal graphs. We first represent the graph under consideration using a "tree-like" graph. This tree is unique and explicitly captures the connectivity information of the graph. Using this tree, our proposed data structure maintains the set of equivalence classes based on an equivalence relation on the set of leaves of the tree. This partition determines a set of edges to be augmented to increase the connectivity of the graph by one. Based on our data structure, we present a new combinatorial analysis and an elegant proof of correctness of our linear-time algorithm for an optimum connectivity augmentation. The novelty is in the data structure which is a unified framework for all three augmentations. As far as the run-time analysis is concerned, given the associated tree, our approach yields an augmentation set in linear time. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of testing an arbitrary digraph G = (V,E) for upward planarity. In particular we describe two fixed-parameter tractable algorithms for testing the upward planarity of G. The first algorithm that we present can test the upward planarity of G in O(2t · t! · |V|2)-time where t is the number of triconnected components of G. The second algorithm that we present uses a standard technique known as kernelisation and can test the upward planarity of G in O(|V|2 + k4 · (2k)!)-time, where k = |E| - |V|. [ABSTRACT FROM AUTHOR]

In this paper we present the first distributed algorithm on general graphs for the Minimum Degree Spanning Tree problem. The problem is NP-hard in sequential. Our algorithm give a Spanning Tree of a degree at most 1 from the optimal. The resulting distributed algorithm is asynchronous, it works for named asynchronous arbitrary networks and achieves O(|V|) time complexity and O(|V||E|) message complexity. [ABSTRACT FROM AUTHOR]

The P[sub 4] is the induced path of four vertices. The gem consists of a P[sub 4] with an additional universal vertex being completely adjacent to the P[sub 4], and the co-gem is its complement graph. Gem- and co-gem-free graphs generalize the popular class of cographs (i. e. P[sub 4]-free graphs). The tree structure and algebraic generation of cographs has been crucial for several concepts of graph decomposition such as modular and homogeneous decomposition. Moreover, it is fundamental for the recently introduced concept of clique-width of graphs which extends the famous concept of treewidth. It is well-known that the cographs are exactly those graphs of clique-width at most 2. In this paper, we show that the clique-width of gem- and co-gem-free graphs is at most 16. [ABSTRACT FROM AUTHOR]

Lai and Leinwand have shown that an arbitrary plane (i.e., embedded planar) graph G can be transformed, by adding crossover vertices, into a new plane graph G' admitting a rectangular dual. Moreover, they conjectured that finding a minimum set of such crossover vertices is an NP-complete problem. In this paper it is shown that the above problem can be resolved in polynomial time by reducing it to a graph covering problem, and an efficient algorithm for finding a minimum set of edges on which to insert the crossover vertices is also presented. [ABSTRACT FROM AUTHOR]