Displaying similar documents to “Algorithm 36. Transitive closure of a graph”

A linear algorithm for the two paths problem on permutation graphs

C.P. Gopalakrishnan, C. Pandu Rangan (1995)

Discussiones Mathematicae Graph Theory

Similarity:

The 'two paths problem' is stated as follows. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two vertex-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂ respectively. In this paper we give a linear (O(|V|+ |E|)) algorithm to solve the above problem on a permutation graph.

Extending the MAX Algorithm for Maximum Independent Set

Ngoc C. Lê, Christoph Brause, Ingo Schiermeyer (2015)

Discussiones Mathematicae Graph Theory

Similarity:

The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.

A factor graph based genetic algorithm

B. Hoda Helmi, Adel T. Rahmani, Martin Pelikan (2014)

International Journal of Applied Mathematics and Computer Science

Similarity:

We propose a new linkage learning genetic algorithm called the Factor Graph based Genetic Algorithm (FGGA). In the FGGA, a factor graph is used to encode the underlying dependencies between variables of the problem. In order to learn the factor graph from a population of potential solutions, a symmetric non-negative matrix factorization is employed to factorize the matrix of pair-wise dependencies. To show the performance of the FGGA, encouraging experimental results on different separable...

Edge-disjoint paths in permutation graphs

C. P. Gopalakrishnan, C. Pandu Rangan (1995)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we consider the following problem. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two edge-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂, respectively. We give a linear (O(|V|+|E|)) algorithm to solve this problem on a permutation graph.