All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 8 Next

Displaying 141 – 160 of 181

Showing per page

Exact double domination in graphs

Mustapha Chellali, Abdelkader Khelladi, Frédéric Maffray (2005)

Discussiones Mathematicae Graph Theory

In a graph a vertex is said to dominate itself and all its neighbours. A doubly dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. A doubly dominating set is exact if every vertex of G is dominated exactly twice. We prove that the existence of an exact doubly dominating set is an NP-complete problem. We show that if an exact double dominating set exists then all such sets have the same size, and we establish bounds on this size. We give a constructive...

Exemples de classes d'automates cellulaires

Marianne Delorme, Jacques Mazoyer (2008)

RAIRO - Theoretical Informatics and Applications

Lorsqu'on observe des orbites de certains automates cellulaires, on peut penser qu'elles apparaissent comme des mélanges d'orbites d'autres automates (composants). Dans cet article, nous tentons de comprendre ce phénomène en construisant un hybride de deux automates au moyen d'un troisième. Deux types d'automates cellulaires sont introduits : les captifs et les foulards. Nous comparons des propriétés de ces hybrides dans le cadre des classifications algébriques introduites par [B. Martin...

Existence of an infinite ternary 64-abelian square-free word

Mari Huova (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We consider a recently defined notion of k-abelian equivalence of words by concentrating on avoidance problems. The equivalence class of a word depends on the numbers of occurrences of different factors of length k for a fixed natural number k and the prefix of the word. We have shown earlier that over a ternary alphabet k-abelian squares cannot be avoided in pure morphic words for any natural number k. Nevertheless, computational experiments support the conjecture that even 3-abelian squares can...

Experimental analysis of some computation rules in a simple parallel reasoning system for the ALC description logic

Adam Meissner (2011)

International Journal of Applied Mathematics and Computer Science

A computation rule determines the order of selecting premises during an inference process. In this paper we empirically analyse three particular computation rules in a tableau-based, parallel reasoning system for the ALC description logic, which is built in the relational programming model in the Oz language. The system is constructed in the lean deduction style, namely, it has the form of a small program containing only basic mechanisms, which assure soundness and completeness of reasoning. In...

Experiments with two Approaches for Tracking Drifting Concepts

Koychev, Ivan (2007)

Serdica Journal of Computing

This paper addresses the task of learning classifiers from streams of labelled data. In this case we can face the problem that the underlying concepts can change over time. The paper studies two mechanisms developed for dealing with changing concepts. Both are based on the time window idea. The first one forgets gradually, by assigning to the examples weight that gradually decreases over time. The second one uses a statistical test to detect changes in concept and then optimizes the size of the...

Experiments with variants of ant algorithms.

Thomas Stützle, Sebastian Linke (2002)

Mathware and Soft Computing

A number of extensions of Ant System, the first ant colony optimization (ACO) algorithm, were proposed in the literature. These extensions typically achieve much improved computational results when compared to the original Ant System. However, many design choices of Ant System are left untouched including the fact that solutions are constructed, that real-numbers are used to simulate pheromone trails, and that explicit pheromone evaporation is used. In this article we experimentally investigate...

Explicit integration of equations of motion solved on computer cluster

Rek, Václav (2019)

Programs and Algorithms of Numerical Mathematics

In the last decade the dramatic onset of multicore and multi-processor systems in combination with the possibilities which now provide modern computer networks have risen. The complexity and size of the investigated models are constantly increasing due to the high computational complexity of computational tasks in dynamics and statics of structures, mainly because of the nonlinear character of the solved models. Any possibility to speed up such calculation procedures is more than desirable. This...

Exploiting tensor rank-one decomposition in probabilistic inference

Petr Savický, Jiří Vomlel (2007)

Kybernetika

We propose a new additive decomposition of probability tables – tensor rank-one decomposition. The basic idea is to decompose a probability table into a series of tables, such that the table that is the sum of the series is equal to the original table. Each table in the series has the same domain as the original table but can be expressed as a product of one- dimensional tables. Entries in tables are allowed to be any real number, i. e. they can be also negative numbers. The possibility of having...

Exploiting the structure of conflict graphs in high level synthesis

Klaus Jansen (1994)

Commentationes Mathematicae Universitatis Carolinae

In this paper we analyze the computational complexity of a processor optimization problem. Given operations with interval times in a branching flow graph, the problem is to find an assignment of the operations to a minimum number of processors. We analyze the complexity of this assignment problem for flow graphs with a constant number of program traces and a constant number of processors.

Exploiting Tree Decomposition for Guiding Neighborhoods Exploration for VNS

Mathieu Fontaine, Samir Loudni, Patrice Boizumault (2013)

RAIRO - Operations Research - Recherche Opérationnelle

Tree decomposition introduced by Robertson and Seymour aims to decompose a problem into clusters constituting an acyclic graph. There are works exploiting tree decomposition for complete search methods. In this paper, we show how tree decomposition can be used to efficiently guide local search methods that use large neighborhoods like VNS. We propose DGVNS (Decomposition Guided VNS) which uses the graph of clusters in order to build neighborhood structures enabling better diversification and intensification....

Currently displaying 141 – 160 of 181