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 16 Next

Displaying 301 – 320 of 924

Showing per page

A note on certain ergodicity coeflcients

Francesco Tudisco (2015)

Special Matrices

We investigate two ergodicity coefficients ɸ ∥∥ and τn−1, originally introduced to bound the subdominant eigenvalues of nonnegative matrices. The former has been generalized to complex matrices in recent years and several properties for such generalized version have been shown so far.We provide a further result concerning the limit of its powers. Then we propose a generalization of the second coefficient τ n−1 and we show that, under mild conditions, it can be used to recast the eigenvector problem...

A note on Coinduction and Weak Bisimilarity for While Programs

J. J.M.M. Rutten (2010)

RAIRO - Theoretical Informatics and Applications

An illustration of coinduction in terms of a notion of weak bisimilarity is presented. First, an operational semantics 𝒪 for while programs is defined in terms of a final automaton. It identifies any two programs that are weakly bisimilar, and induces in a canonical manner a compositional model 𝒟 . Next 𝒪 = 𝒟 is proved by coinduction.

A note on constructing infinite binary words with polynomial subword complexity

Francine Blanchet-Sadri, Bob Chen, Sinziana Munteanu (2013)

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

Most of the constructions of infinite words having polynomial subword complexity are quite complicated, e.g., sequences of Toeplitz, sequences defined by billiards in the cube, etc. In this paper, we describe a simple method for constructing infinite words w over a binary alphabet  { a,b }  with polynomial subword complexity pw. Assuming w contains an infinite number of a’s, our method is based on the gap function which gives the distances between consecutive b’s. It is known that if the gap function...

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 dual approximation algorithms for class constrained bin packing problems

Eduardo C. Xavier, Flàvio Keidi Miyazawa (2009)

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

In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity 1 , and n items of Q different classes, each item e with class c e and size s e . The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size d . In...

A note on dual approximation algorithms for class constrained bin packing problems

Eduardo C. Xavier, Flàvio Keidi Miyazawa (2008)

RAIRO - Theoretical Informatics and Applications

In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity 1, and n items of Q different classes, each item e with class ce and size se. The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size...

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

Marcia R. Cerioli, Luerbio Faria, Talita O. Ferreira, Fábio Protti (2011)

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

A unit disk graph is the intersection graph of a family of unit disks in the plane. If the disks do not overlap, it is also a unit coin graph or penny graph. 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 3-approximation...

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

Marcia R. Cerioli, Luerbio Faria, Talita O. Ferreira, Fábio Protti (2011)

RAIRO - Theoretical Informatics and Applications

A unit disk graph is the intersection graph of a family of unit disks in the plane. If the disks do not overlap, it is also a unit coin graph or penny graph. 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 3-approximation...

Currently displaying 301 – 320 of 924