Page 1 Next

Displaying 1 – 20 of 254

Showing per page

A factor graph based genetic algorithm

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

International Journal of Applied Mathematics and Computer Science

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 problems...

A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs

Yury Metelsky, Kseniya Schemeleva, Frank Werner (2017)

Discussiones Mathematicae Graph Theory

We characterize the class [...] L32 L 3 2 of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 L 3 2 in the class of threshold graphs, where n is the number of vertices of a tested graph.

A linear algorithm for the two paths problem on permutation graphs

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

Discussiones Mathematicae Graph Theory

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.

A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

Markov, Minko, Ionut Andreica, Mugurel, Manev, Krassimir, Tapus, Nicolae (2012)

Serdica Journal of Computing

ACM Computing Classification System (1998): G.2.2.We propose an algorithm that computes the length of a longest path in a cactus graph. Our algorithm can easily be modified to output a longest path as well or to solve the problem on cacti with edge or vertex weights. The algorithm works on rooted cacti and assigns to each vertex a two-number label, the first number being the desired parameter of the subcactus rooted at that vertex. The algorithm applies the divide-and-conquer approach and computes...

A Metaheuristic Approach to Solving the Generalized Vertex Cover Problem

Milanović, Marija (2010)

Mathematica Balkanica New Series

AMS Subj. Classification: 90C27, 05C85, 90C59The topic is related to solving the generalized vertex cover problem (GVCP) by genetic algorithm. The problem is NP-hard as a generalization of well-known vertex cover problem which was one of the first problems shown to be NP-hard. The definition of the GVCP and basics of genetic algorithms are described. Details of genetic algorithm and numerical results are presented in [8]. Genetic algorithm obtained high quality solutions in a short period of time.

A note on domination in bipartite graphs

Tobias Gerlach, Jochen Harant (2002)

Discussiones Mathematicae Graph Theory

DOMINATING SET remains NP-complete even when instances are restricted to bipartite graphs, however, in this case VERTEX COVER is solvable in polynomial time. Consequences to VECTOR DOMINATING SET as a generalization of both are discussed.

A note on on-line ranking number of graphs

Gabriel Semanišin, Roman Soták (2006)

Czechoslovak Mathematical Journal

A k -ranking of a graph G = ( V , E ) is a mapping ϕ V { 1 , 2 , , k } such that each path with endvertices of the same colour c contains an internal vertex with colour greater than c . The ranking number of a graph G is the smallest positive integer k admitting a k -ranking of G . In the on-line version of the problem, the vertices v 1 , v 2 , , v n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G [ { v 1 , v 2 , , v i } ] are known when the colour for the vertex v i has to be chosen. The on-line ranking number of a graph G is the smallest...

A polyhedral study of a two level facility location model

Mourad Baïou, Francisco Barahona (2014)

RAIRO - Operations Research - Recherche Opérationnelle

We study an uncapacitated facility location model where customers are served by facilities of level one, then each level one facility that is opened must be assigned to an opened facility of level two. We identify a polynomially solvable case, and study some valid inequalities and facets of the associated polytope.

A polynomial algorithm for minDSC on a subclass of series Parallel graphs

Salim Achouri, Timothée Bossart, Alix Munier-Kordon (2009)

RAIRO - Operations Research

The aim of this paper is to show a polynomial algorithm for the problem minimum directed sumcut for a class of series parallel digraphs. The method uses the recursive structure of parallel compositions in order to define a dominating set of orders. Then, the optimal order is easily reached by minimizing the directed sumcut. It is also shown that this approach cannot be applied in two more general classes of series parallel digraphs.

Currently displaying 1 – 20 of 254

Page 1 Next