Currently displaying 1 – 7 of 7

Showing per page

Order by Relevance | Title | Year of publication

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

Carlos MartinhonFábio Protti — 2011

RAIRO - Theoretical Informatics and Applications

A vertex of a graph = () is said to be by M V if the majority of the elements of the neighborhood of  (including itself) belong to . The set is a in if every vertex i V is controlled by . Given a set M V and two graphs = ( V , E 1 ) and = ( V , E 2 ) where E 1 E 2 , the consists of deciding whether there exists a sandwich graph = () (, a graph where E 1 E 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 graph...

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

Carlos MartinhonFábio Protti — 2011

RAIRO - Theoretical Informatics and Applications

A vertex of a graph = () is said to be by M V if the majority of the elements of the neighborhood of  (including itself) belong to . The set is a in if every vertex i V is controlled by . Given a set M V and two graphs = ( V , E 1 ) and = ( V , E 2 ) where E 1 E 2 , the consists of deciding whether there exists a sandwich graph = () (, a graph where E 1 E 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 graph...

A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation

Marcia R. CerioliLuerbio FariaTalita O. FerreiraFábio Protti — 2011

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

A is the intersection graph of a family of unit disks in the plane. If the disks do not overlap, it is also a or . It is known that finding a maximum independent set in a unit disk graph is a NP-hard problem. In this work we extend this result to penny graphs. Furthermore, we prove that finding a minimum clique partition in a penny graph is also NP-hard, and present two linear-time approximation algorithms for the computation of clique partitions: a -approximation algorithm for unit disk graphs...

Parity codes

Paulo E. D. PintoFábio ProttiJayme L. Szwarcfiter — 2005

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

Motivated by a problem posed by Hamming in 1980, we define even codes. They are Huffman type prefix codes with the additional property of being able to detect the occurrence of an odd number of 1-bit errors in the message. We characterize optimal even codes and describe a simple method for constructing the optimal codes. Further, we compare optimal even codes with Huffman codes for equal frequencies. We show that the maximum encoding in an optimal even code is at most two bits larger than the maximum...

Parity codes

Paulo E. D. PintoFábio ProttiJayme L. Szwarcfiter — 2010

RAIRO - Theoretical Informatics and Applications

Motivated by a problem posed by Hamming in 1980, we define even codes. They are Huffman type prefix codes with the additional property of being able to detect the occurrence of an odd number of 1-bit errors in the message. We characterize optimal even codes and describe a simple method for constructing the optimal codes. Further, we compare optimal even codes with Huffman codes for equal frequencies. We show that the maximum encoding in an optimal even code is at most two bits larger than the maximum...

A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation

Marcia R. CerioliLuerbio FariaTalita O. FerreiraFábio Protti — 2011

RAIRO - Theoretical Informatics and Applications

A is the intersection graph of a family of unit disks in the plane. If the disks do not overlap, it is also a or . It is known that finding a maximum independent set in a unit disk graph is a NP-hard problem. In this work we extend this result to penny graphs. Furthermore, we prove that finding a minimum clique partition in a penny graph is also NP-hard, and present two linear-time approximation algorithms for the computation of clique partitions: a -approximation algorithm for unit disk graphs and...

Page 1

Download Results (CSV)