Planar Polyline Drawings via Graph Transformations

We study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universität Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where $W\leq\lfloor\frac{2n-2}{3}\rfloorWe study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universit?t Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where W ￡ ?\frac2n-23?W\leq\lfloor\frac{2n-2}{3}\rfloor , and W+H ￡ ?\frac4n-43?W+H\leq\lfloor \frac{4n-4}{3}\rfloor . It uses at most ?\frac2n-53?\lfloor\frac{2n-5}{3}\rfloor bends, and each edge uses at most one bend. Our algorithm is area optimal. Compared with the existing area optimal polyline drawing algorithm proposed in Bonichon et al. (Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 2573, pp. 35–46, Springer, Berlin, 2002), our algorithm uses a smaller number of bends. Their bend bound is (n−2).     

On general construction for extended visual cryptography schemes

Numerous visual cryptography schemes (VCSs) have been proposed to protect a secret image with share images. Most VCSs use random-looking shares to code a single binary secret image. Some schemes are designed for color secret images. Droste's [New results on visual cryptography, in: Advances in Cryptology-CRYPTO ’96, Lecture Notes in Computer Science, vol. 1109, Springer, Berlin, 1996, pp. 401-415] (n,n)-VCS is introduced for multiple binary secret images. Extended VCS (EVCS), by Ateniese et al. [Extended capabilities for visual cryptography, Theoretical Computer Science 250 (2001) 143-161], for binary secret image uses meaningful (innocent-looking) shares. In this paper, we start with a more concise derivation of matrix extension in the ECVS model. This is implemented by concatenating an extended matrix to each basis matrix. We then present a general construction method for single or multiple binary/grayscale/color secret images using matrix extension utilizing meaningful shares. The result (k,n)-visual secret sharing schemes are more general than most existing schemes in terms of the secret/share image types. Using our matrix extension algorithm, any existing VCS with random-looking shares can be easily modified to utilize meaningful shares. The effectiveness of our schemes is demonstrated by real examples.     

Simulation of simultaneous safe recursion over an arbitrary structure

In [O. Bournez, F. Cucker, P.J. de Naurois, J.Y. Marion, Computability over an arbitrary structure. Sequential and parallel polynomial time, in: Lecture Notes in Computer Science, vol. 2620, Springer, Berlin, 2003, pp. 185-199] the class of safe recursive functions over an arbitrary structure is defined. A question of simulation of the simultaneous safe recursion by single safe recursion was set. We prove that this simulation is feasible using bounded coding and decoding functions.     

Blind signature and ring signature schemes: Rehabilitation and attack

Blind signature and ring signature are two signature schemes with privacy concern. Zhang [Jianhong Zhang, Linkability analysis of some blind signature schemes, In International Conference on Computational Intelligence and Security 2006, IEEE, vol. 2, 2006, pp. 1367–1370, (Available at http://dx.doi.org/10.1109/ICCIAS.2006.295283.)] analyzed the unlinkability of Zhang and Kim [Fangguo Zhang, Kwangjo Kim, ID-based blind signature and ring signature from pairings, in: Yuliang Zheng (Ed.), Advances in Cryptology — ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, New Zealand, December 1–5, 2002, Proceedings, Lecture Notes in Computer Science, vol. 2501, Springer, 2002, pp. 533–547], Huang et al. [Zhenjie Huang, Kefei Chen, Yumin Wang, Efficient identity-based signatures and blind signatures, in: Yvo Desmedt, Huaxiong Wang, Yi Mu, Yongqing Li (Eds.), Cryptology and Network Security, 4th International Conference, CANS 2005, Xiamen, China, December 14–16, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3810, Springer, 2005, pp. 120–133] and Wu et al. [Qianhong Wu, Willy Susilo, Yi Mu, Fangguo Zhang, Efficient partially blind signatures with provable security, in: Osvaldo Gervasi, Marina L. Gavrilova, (Eds.), Computational Science and Its Applications — ICCSA 2007, International Conference, Kuala Lumpur, Malaysia, August 26–29, 2007. Proceedings. Part III, Lecture Notes in Computer Science, vol. 4707, Springer, 2007, pp. 1096–1105] and claimed that they are indeed linkable. On the other hand, Gamage et al. [Chandana Gamage, Ben Gras, Bruno Crispo, Andrew S. Tanenbaum, An identity-based ring signature scheme with enhanced privacy, Securecomm and Workshops 2006, IEEE, 2006, pp. 1–5, (Available at http://dx.doi.org/10.1109/SECCOMW.2006.359554)] claimed that the scheme of Chow et al. [Sherman S.M. Chow, Siu-Ming Yiu, Lucas Chi Kwong Hui, Efficient identity based ring signature, in: John Ioannidis, Angelos D. Keromytis, Moti Yung (Eds.), Applied Cryptography and Network Security, Third International Conference, ACNS 2005, New York, NY, USA, June 7–10, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3531, 2005, pp. 499–512] is vulnerable to key exposure attack. This paper shows that all these claims are incorrect. Furthermore, we show that the scheme proposed by Gamage et al. [Chandana Gamage, Ben Gras, Bruno Crispo, Andrew S. Tanenbaum, An identity-based ring signature scheme with enhanced privacy, Securecomm and Workshops 2006, IEEE, 2006, pp. 1–5, (Available at http://dx.doi.org/10.1109/SECCOMW.2006.359554)] which aimed to provide enhanced privacy actually has privacy level reduced. We hope this work can pinpoint the standard one should use when analyzing the unlinkability of blind signatures and the anonymity of ring signatures.     

Using 5-isogenies to quintuple points on elliptic curves

Finding multiples of points on elliptic curves is the most important computation in elliptic curve cryptography. Extending the work of C. Doche, T. Icart, and D. Kohel (Efficient scalar multiplication by isogeny decomposition, in: M. Yung, Y. Dodis, A. Kiayias, T.G. Malkin (Eds.), Public Key Cryptography 2006, in: Lecture Notes in Comput. Sci., vol. 3958, Springer, Heidelberg, 2006, pp. 191-206) we use 5-isogenies to compute multiples of a point on an elliptic curve. Specifically, we find explicit formulas for quintupling a point. We compare the results with other published formulas for quintupling. We find that when the point is represented in Jacobian coordinates with z=1, our method is potentially among the fastest on specially chosen elliptic curves. We also see that using l-isogenies to compute the multiplication by l map (for l larger than five) is unlikely to be more efficient than other techniques.     

Focus points and convergent process operators: a proof strategy for protocol verification

We present a method for efficiently providing algebraic correctness proofs for communication systems. It is described in the setting of μCRL [J.F. Groote, A. Ponse, The syntax and semantics of μCRL, in: A. Ponse, C. Verhoef, S.F.M. van Vlijmen (Eds.), Algebra of Communicating Processes, Workshops in Computing, Springer, Berlin, 1994, pp. 26–62] which is, roughly, ACP [J.C.M. Baeten, W.P. Weijland, Process Algebra, Cambridge Tracts in Theoretical Computer Science, vol. 18, Cambridge University Press, Cambridge 1990, J.A. Bergstra, J.W. Klop, The algebra of recursively defined processes and the algebra of regular processes, in: Proceedings of the 11th ICALP, Antwerp, Lecture Notes in Computer Science, vol. 172, Springer, Berlin, 1984, pp. 82–95] extended with a formal treatment of the interaction between data and processes. The method incorporates assertional methods, such as invariants and simulations, in an algebraic framework, and centers around the idea that the state spaces of distributed systems are structured as a number of cones with focus points. As a result, it reduces a large part of algebraic protocol verification to the checking of a number of elementary facts concerning data parameters occurring in implementation and specification. The resulting method has been applied to various non-trivial case studies of which a number have been verified mechanically with the theorem checker PVS. In this paper the strategy is illustrated by several small examples and one larger example, the Concurrent Alternating Bit Protocol (CABP).     

Comparison and improvement of tangent estimators on digital curves

Many contour-based applications rely on the estimation of the geometry of the shape, such as pattern recognition or classification methods. This paper proposes a comprehensive evaluation on the problem of tangent estimators on digital curves. The methods taken into account use different paradigms: approximation and digital geometry. In the former paradigm, methods based on polynomial fitting, smoothing and filtering are reviewed. In the latter case of digital geometry, we consider two methods that mainly rely on digital straight line recognition [J.-O. Lachaud, A. Vialard, F. de Vieilleville, Fast, accurate and convergent tangent estimation on digital contours, Image and Vision Computing 25(10) (2007) 1572-1587] and optimization [B. Kerautret, J.-O. Lachaud, Robust estimation of curvature along digital contours with global optimization, in: Proceedings of Discrete Geometry for Computer Imagery, Lyon, France, Lecture Notes in Computer Science, vol. 4992, Springer, Berlin, 2008]. The comparison takes into account objective criteria such as multi-grid convergence, average error, maximum error, isotropy and length estimation. Experiments underline that adaptive methods based on digital straight line recognition often propose a good trade-off between time and precision and that if precision is to be sought, non-adaptive methods can be easily transformed into adaptive methods to get more accurate estimations.     

Computing upper and lower bounds of rotation angles from digital images

Rotations in the discrete plane are important for many applications such as image matching or construction of mosaic images. We suppose that a digital image A is transformed to another digital image B by a rotation. In the discrete plane, there are many angles giving the rotation from A to B, which we call admissible rotation angles from A to B. For such a set of admissible rotation angles, there exist two angles that achieve the lower and the upper bounds. To find those lower and upper bounds, we use hinge angles as used in Nouvel and Rémila [Incremental and transitive discrete rotations, in: R. Reulke, U. Eckardt, B. Flash, U. Knauer, K. Polthier (Eds.), Combinatorial Image Analysis, Lecture Notes in Computer Science, vol. 4040, Springer, Berlin, 2006, pp. 199-213]. A sequence of hinge angles is a set of particular angles determined by a digital image in the sense that any angle between two consecutive hinge angles gives the identical rotation of the digital image. We propose a method for obtaining the lower and the upper bounds of admissible rotation angles using hinge angles from a given Euclidean angle or from a pair of corresponding digital images.     

Expand,Enlarge and Check: New algorithms for the coverability problem of WSTS

In this paper, we present a general algorithmic schema called ‘Expand, Enlarge and Check’ from which new algorithms for the coverability problem of WSTS can be constructed. We show here that our schema allows us to define forward algorithms that decide the coverability problem for several classes of systems for which the Karp and Miller procedure cannot be generalized, and for which no complete forward algorithms were known. Our results have important applications for the verification of parameterized systems and communication protocols.A preliminary version of this paper has been published as [Geeraerts et al., Expand, enlarge and check: new algorithms for the coverability problem of WSTS, in: Proceedings of the 24th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 04), Lecture Notes in Computer Science, vol. 3328, Springer, Berlin, 2004, pp. 287–298] in the proceedings of FST&TCS 2004.     

The mutual exclusion scheduling problem for permutation and comparability graphs

In this paper, we consider the mutual exclusion scheduling problem for comparability graphs. Given an undirected graph G and a fixed constant m, the problem is to find a minimum coloring of G such that each color is used at most m times. The complexity of this problem for comparability graphs was mentioned as an open problem by Möhring [Problem 9.10, in: I. Rival (Ed.), Graphs and Orders, Reidel, Dordrecht, 1985, p. 583] and for permutation graphs (a subclass of comparability graphs) as an open problem by Lonc [On complexity of some chain and antichain partition problem, in: G. Schmidt, R. Berghammer (Eds.), Graph Theoretical Concepts in Computer Science, WG 91, Lecture Notes in Computer Science, vol. 570, 1999, pp. 97–104]. We prove that this problem is already NP-complete for permutation graphs and for each fixed constant m⩾6.     

A new model for selfish routing

In this work, we introduce and study a new, potentially rich model for selfish routing over non-cooperative networks, as an interesting hybridization of the two prevailing such models, namely the KPmodel [E. Koutsoupias, C.H. Papadimitriou, Worst-case equilibria, in: G. Meinel, S. Tison (Eds.), Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, in: Lecture Notes in Computer Science, vol. 1563, Springer-Verlag, 1999, pp. 404–413] and the Wmodel [J.G. Wardrop, Some theoretical aspects of road traffic research, Proceedings of the of the Institute of Civil Engineers 1 (Pt. II) (1952) 325–378].     

Strong normalization proofs by CPS-translations

This paper proposes a new proof method for strong normalization of classical natural deduction and calculi with control operators. For this purpose, we introduce a new CPS-translation, continuation and garbage passing style (CGPS ) translation. We show that this CGPS-translation method gives simple proofs of strong normalization of λμ_→∧∨⊥, which is introduced in [P. de Groote, Strong normalization of classical natural deduction with disjunction, in: S. Abramsky (Ed.), Typed Lambda Calculi and Applications, 5th International Conference, TLCA 2001, in: Lecture Notes in Comput. Sci., vol. 2044, Springer, Berlin, 2001, pp. 182-196] by de Groote and corresponds to the classical natural deduction with disjunctions and permutative conversions.     

Adaptive thresholding of tomograms by projection distance minimization

Segmentation is an important step to obtain quantitative information from tomographic data sets. However, it is usually not possible to obtain an accurate segmentation based on a single, global threshold. Instead, local thresholding schemes can be applied that use a varying threshold. Selecting the best local thresholds is not a straightforward task, as local image features often do not provide sufficient information for choosing a proper threshold.Recently, the concept of projection distance was proposed by the authors as a new criterion for evaluating the quality of a tomogram segmentation [K.J. Batenburg, J. Sijbers, Automatic threshold selection for tomogram segmentation by reprojection of the reconstructed image, in: Computer Analysis of Images and Patterns, in: Lecture Notes in Computer Science, vol. 4673, Springer, Berlin/Heidelberg, 2007, pp. 563-570.]. In this paper, we describe how projection distance minimization (PDM) can be used to select local thresholds, based on the available projection data from which the tomogram was initially computed.The results of several experiments are presented in which our local thresholding approach is compared with alternative thresholding methods. These results demonstrate that the local thresholding approach yields segmentations that are significantly more accurate compared to previously published methods, in particular when the initial reconstruction contains artifacts.     

Optimal prefix and suffix queries on texts

In this paper, we study a restricted version of the position restricted pattern matching problem introduced and studied by Mäkinen and Navarro [V. Mäkinen, G. Navarro, Position-restricted substring searching, in: J.R. Correa, A. Hevia, M.A. Kiwi (Eds.), LATIN, in: Lecture Notes in Computer Science, vol. 3887, Springer, 2006, pp. 703-714]. In the problem handled in this paper, we are interested in those occurrences of the pattern that lies in a suffix or in a prefix of the given text. We achieve optimal query time for our problem against a data structure which is an extension of the classic suffix tree data structure. The time and space complexity of the data structure is dominated by that of the suffix tree. Notably, the (best) algorithm by Mäkinen and Navarro, if applied to our problem, gives sub-optimal query time and the corresponding data structure also requires more time and space.     

Orderly communication in the Ambient Calculus

The Ambient Calculus (henceforth, AC) was developed by Cardelli and Gordon as a formal framework to study issues of mobility and migrant code (In: Nivat M, editor. FoSSaCS ’98, Lecture Notes in Computer Science, vol. 1378. Berlin: Springer, 1998. p. 140–55). We present a type system for AC that allows the type of exchanged data within the same ambient to vary over time. Our type system assigns what we call behaviors to processes; a denotational semantics of behaviors is proposed, here called trace semantics, underlying much of the remaining analysis. We state and prove a subject reduction property for our typed version of AC. Based on techniques borrowed from finite automata theory, type checking of fully type-annotated processes is shown to be decidable. We show that the typed version of AC originally proposed by Cardelli and Gordon (In: POPL’99, San Antonio, TX. New York: ACM Press, 1999. p. 79–92) can be naturally embedded into our typed version of AC.     

Power attacks on a side-channel resistant elliptic curve implementation

At ISC 2001 a method for securing elliptic curve point multiplication against side-channel attacks has been proposed by Möller [Lecture Notes in Comput. Sci., vol. 2200, Springer-Verlag, Berlin, 2001, pp. 324-334]. We show that this method does not offer acceptable security. Namely, differential and simple power analysis techniques may reveal the complete secret key.     

The effect of malformed tiles on tile assemblies within the kinetic tile assembly model

Many different constructions of proofreading tile sets have been proposed in the literature to reduce the effect of deviations from ideal behaviour of the dynamics of the molecular tile self-assembly process. In this paper, we consider the effect on the tile assembly process of a different kind of non-ideality, namely, imperfections in the tiles themselves. We assume a scenario in which some small proportion of the tiles in a tile set are “malformed”. We study, through simulations, the effect of such malformed tiles on the self-assembly process within the kinetic Tile Assembly Model (kTAM). Our simulation results show that some tile set constructions show greater error-resilience in the presence of malformed tiles than others. For example, the 2- and 3-way overlay compact proofreading tile sets of Reif et al. (DNA Computing 10, Lecture Notes in Computer Science, vol 3384. Springer, 2005) are able to handle malformed tiles quite well. On the other hand, the snaked proofreading tile set of Chen and Goel (DNA Computing 10, Lecture Notes in Computer Science, vol 3384. Springer, 2005) fails to form even moderately sized tile assemblies when malformed tiles are present. We show how the Chen–Goel construction may be modified to yield new snaked proofreading tile sets that are resilient not only to errors intrinsic to the assembly process, but also to errors caused by malformed tiles.