An improved derandomized approximation algorithm
for the max-controlled  set problem

Carlos Martinhon; Fábio Protti

Displaying similar documents to “An improved derandomized approximation algorithm for the max-controlled set problem”

An improved derandomized approximation algorithm for the max-controlled set problem

Carlos Martinhon, Fábio Protti (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

A vertex of a graph = () is said to be by $M \subseteq V$ if the majority of the elements of the neighborhood of (including itself) belong to . The set is a in if every vertex $i \in V$ is controlled by . Given a set $M \subseteq V$ and two graphs = ( $V, E_{1}$ ) and = ( $V, E_{2}$ ) where $E_{1} \subseteq E_{2}$ , the consists of deciding whether there exists a sandwich graph = () (, a graph where $E_{1} \subseteq E \subseteq E_{2}$ ) such that is a monopoly in = (). If the answer to the is No, we then consider the , whose objective is to find a sandwich...

About the decision of reachability for register machines

Véronique Cortier (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the decidability of the following problem: given affine functions ƒ,...,ƒ over $ℕ^{k}$ and two vectors $v_{1}, v_{2} \in ℕ^{k}$ , is reachable from by successive iterations of ƒ,...,ƒ (in this given order)? We show that this question is decidable for and undecidable for some fixed .

Cycle and Path Embedding on 5-ary N-cubes

Tsong-Jie Lin, Sun-Yuan Hsieh, Hui-Ling Huang (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study two topological properties of the 5-ary -cube $Q_{n}^{5}$ . Given two arbitrary distinct nodes and in $Q_{n}^{5}$ , we prove that there exists an - path of every length ranging from to 5 - 1, where ≥ 2. Based on this result, we prove that $Q_{n}^{5}$ is 5-edge-pancyclic by showing that every edge in $Q_{n}^{5}$ lies on a cycle of every length ranging from to 5.

A singular perturbation problem in a system of nonlinear Schrödinger equation occurring in Langmuir turbulence

Cédric Galusinski (2010)

ESAIM: Mathematical Modelling and Numerical Analysis

Similarity:

The aim of this work is to establish, from a mathematical point of view, the limit α → +∞ in the system $i \partial_{t} E + \nabla (\nabla . E) - α^{2} \nabla \times \nabla \times E = - {| E |}^{2 σ} E,$ where $E : ℝ^{3} \to ℂ^{3}$ . This corresponds to an approximation which is made in the context of Langmuir turbulence in plasma Physics. The -subcritical (that is 2/3) and the -subcritical (that is 2) are studied. In the physical case = 1, the limit is then studied for the $H^{1} (ℝ^{3})$ norm.