Displaying similar documents to “Minimal 2-dominating sets in trees”

The triangles method to build -trees from incomplete distance matrices

Alain Guénoche, Bruno Leclerc (2010)

RAIRO - Operations Research

Similarity:

A method to infer -trees (valued trees having as set of leaves) from incomplete distance arrays (where some entries are uncertain or unknown) is described. It allows us to build an unrooted tree using only 2-3 distance values between the elements of , if they fulfill some explicit conditions. This construction is based on the mapping between -tree and a weighted generalized 2-tree spanning .

About the choice of the variable to unassign in a decision repair algorithm

Cédric Pralet, Gérard Verfaillie (2010)

RAIRO - Operations Research

Similarity:

The algorithm (Jussien and Lhomme, (2002) 21–45), which has been designed to solve (CSP), can be seen, either (i) as an extension of the classical algorithm with the introduction of a free choice of the variable to which to backtrack in case of inconsistency, or (ii) as a algorithm in the space of the partial consistent variable assignments. or (iii) as a hybridisation between and . Experiments reported in Pralet and Verfailllie (2004) show that some heuristics...

Forbidden Factors and Fragment Assembly

F. Mignosi, A. Restivo, M. Sciortino (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper methods and results related to the notion of minimal forbidden words are applied to the fragment assembly problem. The fragment assembly problem can be formulated, in its simplest form, as follows: reconstruct a word from a given set of substrings () of a word . We introduce an hypothesis involving the set of fragments and the maximal length of the minimal forbidden factors of . Such hypothesis allows us to reconstruct uniquely the word from the set in linear time....

Asymptotic equipartition properties for simple hierarchical and networked structures

Kwabena Doku-Amponsah (2012)

ESAIM: Probability and Statistics

Similarity:

We prove for simple hierarchical structures (modelled as ) and networked structures (modelled as ). For example, for large , a networked data structure consisting of units connected by an average number of links of order   log  can be coded by about  ×  bits, where is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical measures.

Asymptotic equipartition properties for simple hierarchical and networked structures

Kwabena Doku-Amponsah (2012)

ESAIM: Probability and Statistics

Similarity:

We prove for simple hierarchical structures (modelled as ) and networked structures (modelled as ). For example, for large , a networked data structure consisting of units connected by an average number of links of order   log  can be coded by about  ×  bits, where is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical measures.

A Note on Negative Tagging for Least Fixed-Point Formulae

Dilian Gurov, Bruce Kapron (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Proof systems with sequents of the form ⊢ Φ for proving validity of a propositional modal -calculus formula Φ over a set of states in a given model usually handle fixed-point formulae through unfolding, thus allowing such formulae to reappear in a proof. Tagging is a technique originated by Winskel for annotating fixed-point formulae with information about the proof states at which these are unfolded. This information is used later in the proof to avoid unnecessary unfolding,...