Journal: Information Processing Letters

Found 137 papers in total
On the greedy algorithm for the Shortest Common Superstring problem with reversals
On the greedy algorithm for the Shortest Common Superstring problem with reversals
2016,
We study a variation of the classical Shortest Common Superstring (SCS) problem in...
Locating modifications in signed data for partial data integrity
Locating modifications in signed data for partial data integrity
2015,
We consider the problem of detecting and locating modifications in signed data to...
Gossip Latin square and the meet-all gossipers problem
Gossip Latin square and the meet-all gossipers problem
2015,
Given a network of n=2ˆk gossipers, we want to schedule a cyclic calendar of...
Approximability and parameterized complexity of multicover by c-intervals
Approximability and parameterized complexity of multicover by c-intervals
2015,
A c ‐interval is the disjoint union of c intervals over ‐ N . The c...
On the de-randomization of space-bounded approximate counting problems
On the de-randomization of space-bounded approximate counting problems
2015,
It was recently shown that ‐ SVD and matrix inversion can be approximated in...
Tree-core and tree-coritivity of graphs
Tree-core and tree-coritivity of graphs
2015,
A new graph parameter, called tree-coritivity, is introduced in this paper. A...
Approximating the optimal sequence of acquisitions and sales with a capped budget
Approximating the optimal sequence of acquisitions and sales with a capped budget
2015,
We introduce and study the approximability of the following problem. There is a set of...
Incidence coloring of Cartesian product graphs
Incidence coloring of Cartesian product graphs
2015,
For a vertex v∈V(G), the incidence neighborhood of v, denoted by IN(v), is the...
Counting inversions adaptively
Counting inversions adaptively
2015,
Consider a sequence X of n elements, where the number of inversions in X is Inv . We...
Computing the K-terminal reliability of directed path graphs
Computing the K-terminal reliability of directed path graphs
2015,
Let G denote a graph, and K *sube; V ( G ) represent a set of target vertices. Assume...
On commutativity of Discrete Fourier Transform
On commutativity of Discrete Fourier Transform
2015,
In this paper we have studied the commutative properties of general Discrete Fourier...
On Secure Domination in Graphs
On Secure Domination in Graphs
2015,
A set D ⊂ V of a graph G = ( V , E ) is a dominating set of G if every vertex not...
Vertex coloring edge-weighted digraphs
Vertex coloring edge-weighted digraphs
2015,
A coloring of a digraph with non‐negative edge weights is a partition of the...
A note on time-bound hierarchical key assignment schemes
A note on time-bound hierarchical key assignment schemes
2013,
A time‐bound hierarchical key assignment scheme is a method to assign...
Analogues of Chaitin's Omega in the computably enumerable sets
Analogues of Chaitin's Omega in the computably enumerable sets
2013,
We show that there are computably enumerable (c.e.) sets with maximum initial segment...
Ranking, unranking and random generation of extensional acyclic digraphs
Ranking, unranking and random generation of extensional acyclic digraphs
2013,
Extensional acyclic digraphs are acyclic digraphs whose vertices have pairwise...
A new method to determine algebraic expression of power mapping based S-boxes
A new method to determine algebraic expression of power mapping based S-boxes
2013,
Power mapping based S‐boxes, especially those with finite field inversion, have...
Desynchronization attack on RAPP ultralightweight authentication protocol
Desynchronization attack on RAPP ultralightweight authentication protocol
2013,
RAPP (RFID Authentication Protocol with Permutation) is a recently proposed and...
On the complexity of model checking interval-valued discrete time Markov chains
On the complexity of model checking interval-valued discrete time Markov chains
2013,
We investigate the complexity of model checking (finite) interval‐valued...
Parallel parsing of operator precedence grammars
Parallel parsing of operator precedence grammars
2013,
Operator precedence grammars, introduced by Floyd several decades ago, enjoy...
Approximation algorithms for parallel open shop scheduling
Approximation algorithms for parallel open shop scheduling
2013,
This paper investigates the parallel open shop scheduling problem. In this problem...
Nash Equilibria for competitive information diffusion on trees
Nash Equilibria for competitive information diffusion on trees
2013,
We consider the game theoretic model of competitive information diffusion recently...
LP decoding of codes with expansion parameter above 2/3
LP decoding of codes with expansion parameter above 2/3
2013,
Feldman et al. (2007) [3] proved that LP decoding corrects 3 ϵ ‐ 2 2...
Density of straight-line 1-planar graph drawings
Density of straight-line 1-planar graph drawings
2013,
A 1 ‐planar drawing of a graph is such that each edge is crossed at most once....
Papers per page: