Journal: Information Processing Letters

Found 137 papers in total
Chain rotations: A new look at tree distance
Chain rotations: A new look at tree distance
2013,
As well known the rotation distance D ( S , T ) between two binary trees S , T of n...
A simple test on 2-vertex- and 2-edge-connectivity
A simple test on 2-vertex- and 2-edge-connectivity
2013,
Testing a graph on 2‐vertex‐ and 2‐edge‐connectivity are...
Coordination mechanism for selfish scheduling under a grade of service provision
Coordination mechanism for selfish scheduling under a grade of service provision
2013,
In this paper, we study the problem of selfish scheduling game under a grade of...
Minimum feedback arc set of m-free digraphs
Minimum feedback arc set of m-free digraphs
2013,
For a simple digraph G , let β ( G ) be the size of the smallest subset X ⊆...
Trees having many minimal dominating sets
Trees having many minimal dominating sets
2013,
We disprove a conjecture by Skupien that every tree of order n has at most 2 n / 2...
A toughness condition for fractional (k,m) -deleted graphs
A toughness condition for fractional (k,m) -deleted graphs
2013,
Let G be a graph. Let h : E ( G ) → [ 0 , 1 ] be a function. If Σ e ∋ x...
Machine scheduling with contiguous processing constraints
Machine scheduling with contiguous processing constraints
2013,
In classical machine scheduling problems the jobs are independent in general....
Preimage and pseudo-collision attacks on step-reduced SM3 hash function
Preimage and pseudo-collision attacks on step-reduced SM3 hash function
2013,
SM3 [12] is the Chinese cryptographic hash standard which was announced in 2010 and...
An efficient bitwise algorithm for intra-procedural data-flow testing coverage
An efficient bitwise algorithm for intra-procedural data-flow testing coverage
2013,
Data‐flow (DF) testing was introduced to achieve more comprehensive structural...
Free-gram phrase identification for modeling Chinese text
Free-gram phrase identification for modeling Chinese text
2013,
Vector space model using bag of phrases plays an important role in modeling Chinese...
Choosability on H-free graphs
Choosability on H-free graphs
2013,
A graph is H ‐free if it has no induced subgraph isomorphic to H . We determine...
BPA bisimilarity is EXPTIME-hard
BPA bisimilarity is EXPTIME-hard
2013,
Given a basic process algebra (BPA) and two stack symbols, the BPA bisimilarity...
The dissecting power of regular languages
The dissecting power of regular languages
2013,
A recent study on structural properties of regular and context‐free languages...
Semi-online hierarchical scheduling problems with buffer or rearrangements
Semi-online hierarchical scheduling problems with buffer or rearrangements
2013,
In this paper, we consider semi‐online hierarchical scheduling problems on two...
(Non-)existence of polynomial kernels for the Test Cover problem
(Non-)existence of polynomial kernels for the Test Cover problem
2013,
The input of the Test Cover problem consists of a set V of vertices, and a collection...
The complexity of geodesic Voronoi diagrams on triangulated 2-manifold surfaces
The complexity of geodesic Voronoi diagrams on triangulated 2-manifold surfaces
2013,
We study the combinatorial complexity of Voronoi diagram of point sites on a general...
Buffer overflow management with class segregation
Buffer overflow management with class segregation
2013,
We consider a new model for buffer management of network switches with Quality of...
Online version of the theorem of Thue
Online version of the theorem of Thue
2013,
A sequence S is nonrepetitive if no two adjacent blocks of S are the same. In 1906...
Surjective multidimensional cellular automata are non-wandering: A combinatorial proof
Surjective multidimensional cellular automata are non-wandering: A combinatorial proof
2013,
A combinatorial proof that surjective D ‐dimensional CA are...
Online inventory replenishment scheduling of temporary orders
Online inventory replenishment scheduling of temporary orders
2013,
This paper studies the online inventory replenishment scheduling problem, in which...
Line graph operation and small worlds
Line graph operation and small worlds
2013,
Complex networks, such as small world networks, are the focus of recent interest...
Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms
Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms
2013,
In the Split Vertex Deletion problem, given a graph G and an integer k , we ask...
Loss ratio of the EDF scheduling policy with early discarding technique
Loss ratio of the EDF scheduling policy with early discarding technique
2013,
This paper considers a firm real‐time M / M / 1 system, where jobs have...
The 2-valued case of makespan minimization with assignment constraints
The 2-valued case of makespan minimization with assignment constraints
2013,
We consider the following special case of minimizing makespan. A set of jobs J and a...
Papers per page: