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

Page 1 Next

Displaying 1 – 20 of 32

Showing per page

A bound for the rank-one transient of inhomogeneous matrix products in special case

Arthur Kennedy-Cochran-Patrick, Sergeĭ Sergeev, Štefan Berežný (2019)

Kybernetika

We consider inhomogeneous matrix products over max-plus algebra, where the matrices in the product satisfy certain assumptions under which the matrix products of sufficient length are rank-one, as it was shown in [6] (Shue, Anderson, Dey 1998). We establish a bound on the transient after which any product of matrices whose length exceeds that bound becomes rank-one.

A CAT algorithm for the exhaustive generation of ice piles

Paolo Massazza, Roberto Radicioni (2010)

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

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model IPM k (n), a generalization of the sand pile model SPM (n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice IPM k (n): this lets us design an algorithm which generates all the ice piles of IPM k (n) in amortized time O(1) and in space O( n ).

A CAT algorithm for the exhaustive generation of ice piles

Paolo Massazza, Roberto Radicioni (2011)

RAIRO - Theoretical Informatics and Applications

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model IPM k (n), a generalization of the sand pile model SPM (n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice IPM k (n): this lets us design an algorithm which generates all the ice piles of IPM k (n) in amortized time O(1) and in space O( n ).

Algebraic and graph-theoretic properties of infinite n -posets

Zoltán Ésik, Zoltán L. Németh (2005)

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

A Σ -labeled n -poset is an (at most) countable set, labeled in the set Σ , equipped with n partial orders. The collection of all Σ -labeled n -posets is naturally equipped with n binary product operations and n ω -ary product operations. Moreover, the ω -ary product operations give rise to n ...

Algebraic and graph-theoretic properties of infinite n-posets

Zoltán Ésik, Zoltán L. Németh (2010)

RAIRO - Theoretical Informatics and Applications

A Σ-labeled n-poset is an (at most) countable set, labeled in the set Σ, equipped with n partial orders. The collection of all Σ-labeled n-posets is naturally equipped with n binary product operations and nω-ary product operations. Moreover, the ω-ary product operations give rise to nω-power operations. We show that those Σ-labeled n-posets that can be generated from the singletons by the binary and ω-ary product operations form the free algebra on Σ in a variety axiomatizable by an infinite collection...

Boundary of the union of rectangles in the plane

Václav Medek (1983)

Aplikace matematiky

Given n rectangles in a plane whose all sides belong to two perpendicular directions, an algorithm for the construction of the boundary of the union of those rectangles is shown in teh paper.

Census algorithms for chinese remainder pseudorank

David Laing, Bruce Litow (2008)

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

We investigate the density and distribution behaviors of the chinese remainder representation pseudorank. We give a very strong approximation to density, and derive two efficient algorithms to carry out an exact count (census) of the bad pseudorank integers. One of these algorithms has been implemented, giving results in excellent agreement with our density analysis out to 5189 -bit integers.

Census algorithms for chinese remainder pseudorank

David Laing, Bruce Litow (2007)

RAIRO - Theoretical Informatics and Applications

We investigate the density and distribution behaviors of the chinese remainder representation pseudorank. We give a very strong approximation to density, and derive two efficient algorithms to carry out an exact count (census) of the bad pseudorank integers. One of these algorithms has been implemented, giving results in excellent agreement with our density analysis out to 5189-bit integers.

Full approximability of a class of problems over power sets.

Giorgio Ausiello, Alberto Marchetti-Spaccamela, Marco Protasi (1981)

Qüestiió

In this paper results concerning structural and approximability properties of the subclass of NP-Complete Optimization Problems, defined over a lattice are considered. First, various approaches to the concept of Fully Polynomial Approximation Scheme are presented with application to several known problems in the class of NP-Complete Optimization Problems.Secondly, a characterization of full Approximability for the class of Max Subset Problems is introduced.

Currently displaying 1 – 20 of 32

Page 1 Next