Scientific Annals of Computer Science
"Alexandru Ioan Cuza" University of Iaşi
Volume XVI, 2006
New Editorial Team.,
pages 3-4
Gabriel Ciobanu
Abstract |
BibTeX
A new editorial team was working to produce this volume.
The new team consists of Gabriel Ciobanu as Managing Editor and Sorin Iftene as
Assistant Editor, having the support of Dorel Lucanu as a Faculty Council
representative.
It is a good time to thank the previous editorial team led by
Toader Jucan and Ferucio Laurentiu Tiplea.
Under their management, the journal has gained increasing
visibility and importance during the last 15 years.
Secrecy for Security Protocols.,
pages 5-38
Cătălin Bîrjoveanu
Abstract |
BibTeX
Security protocols are prescribed sequences
of interactions between entities designed to
provide various security services across
distributed systems. Security protocols are
often wrong due to the extremely subtle
properties they are supposed to ensure.
Deciding whether or not a security protocol
assures secrecy is one of the main challenge
in this area. Undecidability of secrecy for
security protocols is a well-known issue.
Yet, imposing various (reasonable) restrictions,
subclasses of security protocols for which
secrecy is decidable are obtained.
This paper focuses on the decidability and
complexity of the secrecy problem for bounded
security protocols. Several results on this
field have been developed in the literature,
but some of them are wrong and, furthermore,
it is hard to relate all results due to a large
variety of formalisms used to develop them.
This paper corrects the wrong results identified
and presents all the results obtained, together
with the existing results, under the same formalism,
providing a complete picture of the complexity of
the secrecy problem for bounded security protocols.
Algorithms for Optimally Computing in-line Visibility and Their Applications.,
pages 39-50
Mirel Coşulschi and Mihaela Sterpu
Abstract |
BibTeX
In this paper, we approach a comparative study of two algorithms
for calculating vertical segments visibility in certain
situations. The first algorithm, Visibility, can be easily
classified as a brute-force one, while the second algorithm is
more elaborate, involving a better understanding of the problem
and its peculiarity. A refinement of the second algorithm using
the convex hull of a monotone polygon is derived. A thorough study
of complexity of these algorithms is performed. An application of
the visibility reporting algorithm to the efficient placement of
some facilities in a practical problem is also given.
A Cardinality Inverse Maximum Flow Problem.,
pages 51-62
Adrian Deaconu
Abstract |
BibTeX
Starting from a given feasible flow $f$ in a network $G$,
the least number of modifications to the (lower or/and upper)
arc capacities is searched so that if these modifications
are applied, then $f$ becomes a maximum flow in $G$. If there
are no great restrictions in modifying the capacities of the
arcs, the problem is reduced to a minimum cut problem in a unit
capacity network. Some special cases of the problem are separately discussed.
Secret Sharing Schemes with Applications in Security Protocols.,
pages 63-96
Sorin Iftene
Abstract |
BibTeX
A secret sharing scheme starts with a secret and then derives from it
certain shares (or shadows) which are distributed to some users.
The secret may be recovered only by certain
predetermined groups which belong to the access structure.
Secret sharing schemes have appeared as an elegant solution for the problem
of safeguarding cryptographic keys
and their applications include now threshold cryptographic protocols and
some e-voting or e-auction protocols.
This paper presents the state-of-art in secret sharing.
Solving Optimization Problems using an ACS-based Approach.,
pages 97-107
Camelia M. Pintea and Gabriel Negara
Abstract |
BibTeX
Ant-systems based techniques are using metaheuristics
able to solve $mathcal {NP}$-hard problems. We introduce
a technique based on Ant Colony System. It uses an
extra-exploration phase in order to improve the quality
of the solutions. In our algorithm two ant colonies explore
and exploit the searching space in order to find solutions.
The first colony is called {em exploring colony}. Its main
goal is to generate partial solutions by imposing strategies
for chosing the next steps when exploring the solutions space.
The second colony, the {em exploiting colony}, finds the best
solution combining its own experience with information provided
by the exploring colony. We apply our technique for solving the
Travelling Salesman problem. The solutions are improved using
{em 2-opt} and {em 3-opt} heuristics. The experiments on
problems from {em TSPLIB}, the Traveling Salesman Problem Library,
show encouraging results. The technique could be applied for
solving routing, scheduling and other types of optimization problems.
