18977044
Graph Searching on Some Subclasses of Chordal Graphs
Abstract. In the graph-searching problem, initially a graph with all the edges contaminated is presented. The objective is to obtain a state of the graph in which all the edges are simultaneously cleared by using the least number of searchers. Two variations of the graph-searching problem are considered. One is edge searching, in which an edge is cleared by moving a searcher along this edge, and the other is node searching, in which an edge is cleared by concurrently having searchers on both of its two endpoints. We present a uniform approach to solve the above two variations on several subclasses of chordal graphs. For edge searching, we give an O(mn2) -time algorithm on split graphs (i.e., 1-starlike graphs), an O(m+n) -time algorithm on interval graphs, and an O(mnk) -time algorithm on k -starlike graphs (a generalization of split graphs), for a fixed k\geq 2 , where m and n are the numbers of edges and vertices in the input graph, respectively. There is no polynomial algorithm known previously for any of the above problems. In addition, we also show that the edge-searching problem remains NP-complete on chordal graphs. For node searching, we give an O(mnk) -time algorithm on k -starlike graphs for a fixed k \geq 1 . This result implies that the pathwidth problem on k -starlike graphs can also be solved in this time bound which greatly improves the previous results.
29920941
Counting Clique Trees and Computing Perfect Elimination Schemes in Parallel
Abstract In a previous result, the authors showed that a clique tree of a chordal graph can be constructed in O(log n ) parallel computing time with O( n 3 ) processors on CRCW PRAM, where n is the number of nodes of the graph. In this paper, it will be shown that this result can be extended in two ways. First, we show that from the parallel clique tree constructing algorithm, we can derive an exact formula of counting clique trees of a labeled connected chordal graph. Next, we show that a perfect elimination scheme of a chordal graph can be computed in O(log n ) time with O( n 2 ) processors on CREW PRAM once a clique tree of the graph is given. This implies that a perfect elimination scheme of a chordal graph can be computed in O(log n ) time with O( n 3 ) processors on CRCW PRAM.
45928902
An Efficient Parallel Strategy for Computing K-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees
In this paper, we first develop a parallel algorithm for computingK-terminal reliability, denoted byR(GK), in 2-trees. Based on this result, we can also computeR(GK) in partial 2-trees using a method that transforms, in parallel, a given partial 2-tree into a 2-tree. Finally, we solve the problem of finding most vital edges with respect toK-terminal reliability in partial 2-trees. Our algorithms takeO(logn) time withC(m,n) processors on a CRCW PRAM, whereC(m,n) is the number of processors required to find the connected components of a graph withmedges andnvertices in logarithmic time.
1980858
Edge and Node Searching Problems on Trees
In this paper, we show that there is a natural correspondence between a tree's edge-search strategy and its node-search strategy. By doing so, we simplify the previous linear time algorithm for determining the edge-search number of a tree, and improve the running time of a previous algorithm for constructing an edge-search strategy (or plan) for a tree containing n vertices from O(n log n) to O(n) time.
10538824
Parallel Decomposition of Generalized Series-Parallel Graphs
Generalized series-parallel (GSP) graphs belong to the class of decomposable graphs which can be represented by their decomposition trees. Given a decomposition tree of a GSP graph, there are many graph-theoretic problems which can be solved efficiently. An efficient parallel algorithm for constructing a decomposition tree of a given GSP graph is presented. It takes O(log n) time with C(m, n) processors on a CRCW PRAM, where C(m, n) is the number of processors required to find connected components of a graph with in edges and n vertices in logarithmic time. Based on our algorithmic results, we also derive some properties for GSP graphs, which may be of interest in and of themselves.
12861854
The Recognition of Geodetically Connected Graphs
Abstract Let G = ( V , E ) be a graph with vertex set V of size n and edge set E of size m . A vertex υ ϵ V is called a hinge vertex if the distance of any two vertices becomes longer after v is removed. A graph without hinge vertex is called a hinge-free graph. In general, a graph G is k -geodetically connected or k -GC for short if G can tolerate any k − 1 vertices failures without increasing the distance among all the remaining vertices. In this paper, we show that recognizing a graph G to be k -GC for the largest value of k can be solved in O ( nm ) time. In addition, more efficient algorithms for recognizing the k -GC property on some special graphs are presented. These include the O ( n + m ) time algorithms on strongly chordal graphs (if a strong elimination ordering is given), ptolemaic graphs, and interval graphs, and an O ( n 2 ) time algorithm on undirected path graphs (if a characteristic tree model is given). Moreover, we show that if the input graph G is not hinge-free then finding all hinge vertices of G can be solved in the same time complexity on the above classes of graphs.
30879352
An Ant Colony Optimization Approach to the Degree-Constrained Minimum Spanning Tree Problem
This paper presents the application of an Ant Colony Optimization (ACO) algorithm approach for communications networks design problem. We explore the use of ACO’s for solving a network optimization problem, the degree-constrained minimum spanning tree problem (d-MST), which is a NP-Hard problem. The effectiveness of the proposed algorithm is demonstrated through two kinds of data set: structured hard (SHRD) complete graphs and misleading (M-graph) complete graphs. Empirical results show that ACO performs competitively with other approaches based on evolutionary algorithm (EA) on certain instance set problem.
641485
Mapping XML and relational schemas with Clio
Merging and coalescing data from multiple and diverse sources into different data formats continues to be an important problem in modern information systems. Schema matching (the process of matching elements of a source schema with elements of a target schema) and schema mapping (the process of creating a query that maps between two disparate schemas) are at the heart of data integration systems. We demonstrate Clio, a semi-automatic schema mapping tool developed at the IBM Almaden Research Center. In this paper, we showcase Clio's mapping engine which allows mapping to and from relational and XML schemas, and takes advantage of data constraints in order to preserve data associations.
39997093
Performance of an Ant Colony Optimization (ACO) Algorithm on the Dynamic Load-Balanced Clustering Problem in Ad Hoc Networks
This paper examines the performance of a recently proposed ACO algorithm when applied to the problem of constructing load-balanced clusters in ad hoc networks with node mobility. Performance, in this context, is measured in terms of the magnitude of change in solution quality after nodes move, and reactivity. Reactivity refers to the number of cycles ACO takes to recover from any degradation in solution quality resulting from node movements. Empirical results on 16 problem instances of various sizes revealed a positive correlation
13477825
A HYBRID GENETIC ALGORITHM FOR OPTICAL ORTHOGONAL CODE CONSTRUCTION
Optical orthogonal codes (OOCs) are used to uniquely identify stations within an optical code division multiple access (CDMA) local area network (LAN). Previous efforts in constructing OOCs have focused on the use of deterministic techniques, which relied heavily on the use of Galois fields. These techniques severely restrict the availability of the resulting OOCs. This paper considers an evolutionary approach by proposing a hybrid genetic algorithm (hGA) as a flexible technique to construct OOCs. This hGA uses the simulated annealing (SA) method to generate its initial population. The effectiveness of the proposed hGA for OOC construction is demonstrated in two stages. First, we show that the SA-generated initial population is better than the randomly generated initial population in terms of fitness. Due to this, the hGA is able to converge on average two times faster compared to the use of the GA-only scheme. Second, we compare the code availability and performance of the hGA-constructed OOCs (hGA OOCs) against that of three other OOCs. Through these comparisons, we show why the proposed hGA is a more flexible technique for constructing OOCs with higher availability and better performance.
44418101
Degree-constrained minimum spanning tree
Abstract In this paper the problem of a degree-constrained minimum spanning tree (DCMST) is defined. The problem is formulated as a linear 0–1 integer programming problem. A primal and a dual heuristic (construction) procedure and a branch-and-bound algorithm are proposed to construct a DCMST. These procedures are illustrated with a simple example. Some computational experience with these algorithms is also reported.