Book reviews

L.C.W.Dixon, G.P.Szegö{eds.}: Towards Global Optimisation.. North-Holland Publishing Company, Amsterdam 1975, 472 S., Dfl 95,00.

L.R.A.Casse, W.D.Wallis (eds.): Combinatorial Mathematics IV.. Proceedings of the Fourth Australian Conference, Held at the University of Adelaide, August 27-29, i975. Lecture Notes in Mathematics 560, Springer Verlag, Berlin-Hoidelberg-New York 1976" VII +249 S., DM 24,80.

R.Glowinski, J.L.Lions (eds.): Computing Methods in Applied Sciences and Engineering. Second International Symposium, December 15-19, 1975. Lecture Notes in Economics and Mathematical Systems, Vol. 134. Springer-Verlag Berlin-Heidelberg-New York 1976, VIII +390 S., DM 37.

E.Bohl,L.Collatz, K.P.Hadeler (Hrsg.): Numerik und Anwendungen von Eigenwertaufgaben und Verzweigungsproblemen. Vortragsauszüge der Tagung über Numerik und Anwendung von Eigenwerteufgaben und Verzweigungsproblemen vom 14.-20. November 1976 im Mathematischen Forschungsinstitut Oberwolfach (Schwarzwald). Internationale Schriftenreihe zur Numerischen Mathematik, Vol. 38. Birkhäuser-Verlag Basel 1977, 218 S., sir 42.     

Applications of the complexity space to the General Probabilistic Divide and Conquer Algorithms

Schellekens [M. Schellekens, The Smyth completion: A common foundation for denotational semantics and complexity analysis, in: Proc. MFPS 11, in: Electron. Notes Theor. Comput. Sci., vol. 1, 1995, pp. 535-556], and Romaguera and Schellekens [S. Romaguera, M. Schellekens, Quasi-metric properties of complexity spaces, Topology Appl. 98 (1999) 311-322] introduced a topological foundation to obtain complexity results through the application of Semantic techniques to Divide and Conquer Algorithms. This involved the fact that the complexity (quasi-metric) space is Smyth complete and the use of a version of the Banach fixed point theorem and improver functionals. To further bridge the gap between Semantics and Complexity, we show here that these techniques of analysis, based on the theory of complexity spaces, extend to General Probabilistic Divide and Conquer schema discussed by Flajolet [P. Flajolet, Analytic analysis of algorithms, in: W. Kuich (Ed.), 19th Internat. Colloq. ICALP'92, Vienna, July 1992; Automata, Languages and Programming, in: Lecture Notes in Comput. Sci., vol. 623, 1992, pp. 186-210]. In particular, we obtain a general method which is useful to show that for several recurrence equations based on the recursive structure of General Probabilistic Divide and Conquer Algorithms, the associated functionals have a unique fixed point which is the solution for the corresponding recurrence equation.     

On a relation between the domination number and a strongly connected bidirection of an undirected graph

As a generalization of directed and undirected graphs, Edmonds and Johnson [J. Edmonds, E.L. Johnson, Matching: A well-solved class of linear programs, in: R. Guy, H. Hanani, N. Sauer, J. Schönheim (Eds.), Combinatorial Structures and their Applications, Gordon and Breach, New York, 1970, pp. 88-92] introduced bidirected graphs. A bidirected graph is a graph each arc of which has either two positive end-vertices (tails), two negative end-vertices (heads), or one positive end-vertex (tail) and one negative end-vertex (head). We extend the notion of directed paths, distance, diameter and strong connectivity from directed to bidirected graphs and characterize those undirected graphs that allow a strongly connected bidirection. Considering the problem of finding the minimum diameter of all strongly connected bidirections of a given undirected graph, we generalize a result of Fomin et al. [F.V. Fomin, M. Matamala, E. Prisner, I. Rapaport, Bilateral orientations in graphs: Domination and AT-free classes, in: Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics, GRACO 2001, in: Electronics Notes in Discrete Mathematics, vol. 7, Elsevier Science Publishers, 2001] about directed graphs and obtain an upper bound for the minimum diameter which depends on the minimum size of a dominating set and the number of bridges in the undirected graph.     

An improved bit parallel exact maximum clique algorithm

This paper describes new improvements for BB-MaxClique (San Segundo et al. in Comput Oper Resour 38(2):571–581, 2011), a leading maximum clique algorithm which uses bit strings to efficiently compute basic operations during search by bit masking. Improvements include a recently described recoloring strategy in Tomita et al. (Proceedings of the 4th International Workshop on Algorithms and Computation. Lecture Notes in Computer Science, vol 5942. Springer, Berlin, pp 191–203, 2010), which is now integrated in the bit string framework, as well as different optimization strategies for fast bit scanning. Reported results over DIMACS and random graphs show that the new variants improve over previous BB-MaxClique for a vast majority of cases. It is also established that recoloring is mainly useful for graphs with high densities.     

Decomposition algorithms for the tree edit distance problem

We study the behavior of dynamic programming methods for the tree edit distance problem, such as [P. Klein, Computing the edit-distance between unrooted ordered trees, in: Proceedings of 6th European Symposium on Algorithms, 1998, p. 91–102; K. Zhang, D. Shasha, SIAM J. Comput. 18 (6) (1989) 1245–1262]. We show that those two algorithms may be described as decomposition strategies. We introduce the general framework of cover strategies, and we provide an exact characterization of the complexity of cover strategies. This analysis allows us to define a new tree edit distance algorithm, that is optimal for cover strategies.     

Topological cones: functional analysis in a T<Subscript>0</Subscript>-setting

Already in his PhD Thesis on compact Abelian semigroups under the direction of Karl Heinrich Hofmann the author was lead to investigate locally compact cones (Keimel in Math. Z. 99:205–428, 1967). This happened in the setting of Hausdorff topologies. The theme of topological cones has been reappearing in the author’s work in a non-Hausdorff setting motivated by the needs of mathematical models for a denotational semantics of languages combining probabilistic and nondeterministic choice. This is in the line of common work with Karl Heinrich Hofmann in Continuous Lattices and Domains (Gierz et al. in Encyclopedia of Mathematics and its Applications, vol. 93, 2003). Domain Theory is based on order theoretical notions from which intrinsic non-Hausdorff topologies are derived. Along these lines, domain theoretical variants of (sub-) probability measures have been introduced by Jones and Plotkin (Jones, PhD thesis, 1990; Jones and Plotkin in Proceedings of the Fourth Annual Symposium on Logic in Computer Science, pp. 186–195, 1989). Kirch (Master’s thesis, 1993) and Tix (Master’s thesis, 1995) have extended this theory to a domain theoretical version of measures and they have introduced and studied directed complete partially ordered cones as appropriate structures. Driven by the needs of a semantics for languages combining probability and nondeterminism, Tix (Theor. Comput. Sci 264:205–218, 1999; PhD thesis, 1999) and later on Plotkin and Keimel (Electron. Notes Theor. Comput. Sci. 129:1–104, 2005) developed basic functional analytic tools for these structures. In this paper we extend this theory to topological cones the topologies of which are strongly non-Hausdorff. We carefully introduce these structures and their elementary properties. We prove Hahn-Banach type separation theorems under appropriate local convexity hypotheses. We finally construct a monad assigning to every topological cone C another topological cone the elements of which are nonempty compact convex subsets of C. For proving that this construction has good properties needed for the application in semantics we use the functional analytic tools developed before. Dedicated to Karl Heinrich Hofmann at the occasion of his 75th birthday. Thanks to Gordon Plotkin for numerous discussions. Preliminary results have been announced at MFPS XXIII 20. In his Master’s thesis supervised by the author, B. Cohen 6 has worked out some of those results.     

Some remarks about leaf roots

Nishimura et al. [On graph powers for leaf-labeled trees, J. Algorithms 42 (2002) 69-108] define a k-leaf root of a graph G=(V_G,E_G) as a tree T=(V_T,E_T) such that the vertices of G are exactly the leaves of T and two vertices in V_G are adjacent in G if and only if their distance in T is at most k. Solving a problem posed by Niedermeier [Personal communication, May 2004] we give a structural characterization of the graphs that have a 4-leaf root. Furthermore, we show that the graphs that have a 3-leaf root are essentially the trees, which simplifies a characterization due to Dom et al. [Error compensation in leaf power problems, Algorithmica 44 (2006) 363-381. (A preliminary version appeared under the title “Error compensation in leaf root problems”, in: Proceedings of the 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004), Lecture Notes in Computer Science, vol. 3341, pp. 389-401)] and also a related recognition algorithm due to Nishimura et al. [On graph powers for leaf-labeled trees, J. Algorithms 42 (2002) 69-108].     

Book reviews

Griffiths, D.F. (ed.):Numerical Analysis. Proceedings of the 10th Biennial Conference held at Dundee, Scotland, Jun 28-Juli 1, 1983. Lecture Notes in Mathematics. Vol. 1066. SpringerVerlag Berlin, Heidelberg, New York, Tokyo 1984, XI, 275 p. DM 33.50, ISBN 2-540-13344-5.

Gross, D.; C.M. Harris:Fundamentals of Queueing Theory. 2. Ed. John Wiley & Sons Limited New York, Chichester, Brisbane, Toronto 1985, XII, 587 p., £ 43.95, ISBN0-471-89067-7.

Miklosöko.; J.E.Kotov (eds.):Algorithms, Software and Hardware of Parallel Computers. Springer-Verlag Berlin, Heidelberg, New York, Tokyo 1984, 181 figs., 380 p., DM 89,-,ISBN 3-540-13657-6.

Dolcetta, I.C.; W.H. Fleming; T.Zolezzr (eds.):Recent Mathematical Methods in Dynamic Programming. Proceedings Corti. Rome, Mar 26-28, 1984. Lecture Notes in Mathematics. Vol. 1119. Springer-Verlag Berlin, Heidelberg, New York, Tokyo 1985, VI, 202 S.DM 31,50, ISBN 3-540-15217-2.

Demyanov, V.F.; D.Pallaschke (eds.):Nondifferentiable Optimization:Motivations and Applications. Proceedings, Sopron, Hungary 1984. Lecture Notes in Economics and Mathematical Systems. Vol. 255. Springer-Verlag Berlin, Heidelberg, New York, Tokyo 1985, VI, 349 S.

Kiwiel, K.C.:Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics. VoL 1133. Springer-Verlag Berlin, Heidelberg, New York, Tokyo 1985, 'T1, 362 S., DM 51,50, ISBN 3-540-15642-9.

Remmert, R.:Funktionentheorie. Vol. 1. Grundwisaen Mat.hematik. Vol. 5. Springer-Verlag Berlin, Heidelberg, New York, Tokyo 1984, 65 Abb., XIII, 324 S., DM 44,-, ISBN:3;540-12782-8.

Walsh, G. R.:An Introduction to Linear Programming. 2. Ed. John Wiley & Sons Chichester, New York, Brisbane, Toronto, Singapore 1985, IX, 240 p., ISBN 0-471-90719-7.

Törnig, W.;M. Kaspar:Numerische Ldsung von partiellen Differentialgleichungen der Technik. Mathematische Methoden in der Technik.. Bd.. 1. B. G. Teubner Stuttgart 1985, 181 S., DM 34,-, ISBN 3-519-02613-9.

Neunzert, H.(ed.):Proceedings of the Conference JIathematics in Industry, Oct 24 - 28, 1983 Oberwolfach. B. G. Teubner Stuttgart 1984, 287 S., 52,- DM, ISBN 3-519-02610-4.

Lösch, M.:Fixpunkt-Schätzvertahren für Modelle mit rationaien Erwartungen.. Mathematical Systems in Economics:" Vol. 94. Verlagsgruppe Athenäum, Hain, Hanstein Königstein 1984; 312 S.,DM 68,-,ISBN 3-445-02387-5.

Bultheel, A.; P.Dewilde (eds.):Rational Approximation in Systems Engineering. Birkhäuser Verlag Basel 1983, 244 pp., sFr. 72,-. ISBN 3-7643-3159-3.

Harrison, J. M.:Brownian ])Iotion and Stochastic Flow Systems. John Wiley & Sons New York, Chichester, Brisbane 1985, XIX, 140 pp., 36.95 £ ISBN 471-81939-5.     

Clutter nonidealness

Several key results for set packing problems do not seem to be easily or even possibly transferable to set covering problems, although the symmetry between them. The goal of this paper is to introduce a nonidealness index by transferring the ideas used for the imperfection index defined by Gerke and McDiarmid [Graph imperfection, J. Combin. Theory Ser. B 83 (2001) 58-78]. We found a relationship between the two indices and the strength of facets defined in [M. Goemans, Worst-case comparison of valid inequalities for the TSP, mathematical programming, in: Fifth Integer Programming and Combinatorial Optimization Conference, Lecture Notes in Computer Science, vol. 1084, Vancouver, Canada, 1996, pp. 415-429; M. Goemans, L.A. Hall, The strongest facets of the acyclic subgraph polytope are unknown, in: Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 1084, Springer, Berlin, 1996, pp. 415-429]. We prove that a clutter is as nonideal as its blocker and find some other properties that could be transferred from the imperfection index to the nonidealness index. Finally, we analyze the behavior of the nonidealness index under some clutter operations.     

On the mean number of encryptions for tree-based broadcast encryption schemes

The challenge of stateless-receiver broadcast encryption lies in minimizing storage and the number of encryptions while maintaining system security. Tree-based key distribution schemes offer the best known trade-off between the two parameters. Examples include the complete subtree scheme [D. Wallner, et al., Internet draft, http://www.ietf.org/ID.html [10]; C.K. Wong, et al., in: Proc. SIGCOMM, 1998, pp. 68–79 [11]], the subset difference scheme [D. Naor, et al., in: CRYPTO 2001, Lecture Notes in Comput. Sci., vol. 2139, 2001, pp. 41–62 [7]], and the layered subset difference scheme [D. Halevy, A. Shamir, in: CRYPTO 2002, Lecture Notes in Comput. Sci., vol. 2442, 2002, pp. 47–60 [5]]. We introduce generating functions for this family of schemes, which lead to analysis of the mean number of encryptions over all privileged sets of users. We also derive the mean number of encryptions when the number of privileged users is fixed. We expect that the techniques introduced as well as the results in this work will find applications in related areas.     

An efficiently computed lower bound on the number of recombinations in phylogenetic networks: Theory and empirical study

Phylogenetic networks are models of sequence evolution that go beyond trees, allowing biological operations that are not tree-like. One of the most important biological operations is recombination between two sequences. An established problem [J. Hein, Reconstructing evolution of sequences subject to recombination using parsimony, Math. Biosci. 98 (1990) 185–200; J. Hein, A heuristic method to reconstruct the history of sequences subject to recombination, J. Molecular Evoluation 36 (1993) 396–405; Y. Song, J. Hein, Parsimonious reconstruction of sequence evolution and haplotype blocks: finding the minimum number of recombination events, in: Proceedings of 2003 Workshop on Algorithms in Bioinformatics, Berlin, Germany, 2003, Lecture Notes in Computer Science, Springer, Berlin; Y. Song, J. Hein, On the minimum number of recombination events in the evolutionary history of DNA sequences, J. Math. Biol. 48 (2003) 160–186; L. Wang, K. Zhang, L. Zhang, Perfect phylogenetic networks with recombination, J. Comput. Biol. 8 (2001) 69–78; S.R. Myers, R.C. Griffiths, Bounds on the minimum number of recombination events in a sample history, Genetics 163 (2003) 375–394; V. Bafna, V. Bansal, Improved recombination lower bounds for haplotype data, in: Proceedings of RECOMB, 2005; Y. Song, Y. Wu, D. Gusfield, Efficient computation of close lower and upper bounds on the minimum number of needed recombinations in the evolution of biological sequences, Bioinformatics 21 (2005) i413–i422. Bioinformatics (Suppl. 1), Proceedings of ISMB, 2005, D. Gusfield, S. Eddhu, C. Langley, Optimal, efficient reconstruction of phylogenetic networks with constrained recombination, J. Bioinform. Comput. Biol. 2(1) (2004) 173–213; D. Gusfield, Optimal, efficient reconstruction of root-unknown phylogenetic networks with constrained and structured recombination, J. Comput. Systems Sci. 70 (2005) 381–398] is to find a phylogenetic network that derives an input set of sequences, minimizing the number of recombinations used. No efficient, general algorithm is known for this problem. Several papers consider the problem of computing a lower bound on the number of recombinations needed. In this paper we establish a new, efficiently computed lower bound. This result is useful in methods to estimate the number of needed recombinations, and also to prove the optimality of algorithms for constructing phylogenetic networks under certain conditions [D. Gusfield, S. Eddhu, C. Langley, Optimal, efficient reconstruction of phylogenetic networks with constrained recombination, J. Bioinform. Comput. Biol. 2(1) (2004) 173–213; D. Gusfield, Optimal, efficient reconstruction of root-unknown phylogenetic networks with constrained and structured recombination, J. Comput. Systems Sci. 70 (2005) 381–398; D. Gusfield, Optimal, efficient reconstruction of root-unknown phylogenetic networks with constrained recombination, Technical Report, Department of Computer Science, University of California, Davis, CA, 2004]. The lower bound is based on a structural, combinatorial insight, using only the site conflicts and incompatibilities, and hence it is fundamental and applicable to many biological phenomena other than recombination, for example, when gene conversions or recurrent or back mutations or cross-species hybridizations cause the phylogenetic history to deviate from a tree structure. In addition to establishing the bound, we examine its use in more complex lower bound methods, and compare the bounds obtained to those obtained by other established lower bound methods.     

A dynamic distributed approach to representing proper interval graphs

First studied by Brodal and Fagerberg [G.S. Brodal, R. Fagerberg, Dynamic representation of sparse graphs, in: Algorithms and Data Structures, Proceedings of the 6th International Workshop, Vancouver, Canada, in: Lecture Notes in Computer Science, vol. 1663, Springer-Verlag, 1999], a dynamic adjacency labelling scheme labels the vertices of a graph so that the adjacency of two vertices can be deduced from their labels. The scheme is dynamic in the sense that only a small adjustment must be made to the vertex labels when a small change is made to the graph.Using a centralized dynamic representation of Hell, Shamir and Sharan [P. Hell, R. Shamir, R. Sharan, A fully dynamic algorithm for recognizing and representing proper interval graphs, SIAM Journal on Computing 31 (1) (2001) 289-305], we develop a bit/label dynamic adjacency labelling scheme for proper interval graphs. Our fully dynamic scheme handles vertex deletion/addition and edge deletion/addition in time. Furthermore, our dynamic scheme is error-detecting, as it recognizes when the new graph is not a proper interval graph.     

Propositional belief base merging or how to merge beliefs/goals coming from several sources and some links with social choice theory

We give in this paper new results on merging operators. Those operators aim to define the goals (or beliefs) of an agents' group after the individuals' goals (beliefs). Using the logical framework of Konieczny and Pino Pérez [Proceedings of the Fifth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU'99), Lecture Notes in Artificial Intelligence 1638, 1999, pp. 233–244] we study the relationships between two important sub-families of merging operators: majority operators and arbitration operators. An open question was to know if those two families were disjoint or not. We show that there are operators that belong simultaneously to the two families. Furthermore, the new family introduced allows the user to choose the “consensual level” he wants for his majority operator. We show at the end of this work some relationships between logical belief merging operators and social choice rules.     

Efficient algorithms for Koblitz curves over fields of characteristic three

The nonadjacent form method of Koblitz [Advances in Cryptology (CRYPTO'98), in: Lecture Notes in Comput. Sci., vol. 1462, 1998, pp. 327–337] is an efficient algorithm for point multiplication on a family of supersingular curves over a finite field of characteristic 3. In this paper, a further discussion of the method is given. A window nonadjacent form method is proposed and its validity is proved. Efficient reduction and pre-computations are given. Analysis shows that more than 30% of saving can be achieved.     

An optimal randomized algorithm for d-variate zonoid depth

A randomized linear expected-time algorithm for computing the zonoid depth [R. Dyckerhoff, G. Koshevoy, K. Mosler, Zonoid data depth: Theory and computation, in: A. Prat (Ed.), COMPSTAT 1996—Proceedings in Computational Statistics, Physica-Verlag, Heidelberg, 1996, pp. 235–240; K. Mosler, Multivariate Dispersion, Central Regions and Depth. The Lift Zonoid Approach, Lecture Notes in Statistics, vol. 165, Springer-Verlag, New York, 2002] of a point with respect to a fixed dimensional point set is presented.     

Alternating Paths along Axis-Parallel Segments

It is shown that for a set S of n pairwise disjoint axis-parallel line segments in the plane there is a simple alternating path of length . This bound is best possible in the worst case. In the special case that the n pairwise disjoint axis-parallel line segments are protruded (that is, if the intersection point of the lines through every two nonparallel segments is not visible from both segments), there is a simple alternating path of length n. Work on this paper was partially supported by National Science Foundation grants CCR-0049093 and IIS-0121562. A preliminary version of this paper has appeared in the Proceedings of the 8th International Workshop on Algorithms and Data Structures (Ottawa, ON, 2003), vol. 2748 of Lecture Notes on Computer Science, Springer, Berlin, 2003, pp. 389–400.     

Order 24 Hadamard matrices of character at least 3

It is determined that the number of inequivalent Hadamard matrices of order 24 and character at least 3 is at least 29. N. Ito, J. Leon and the author are determining the equivalence classes among the 133 matrices given here. The author has shown elsewhere [in “Theory and Applications of Graphs,” Lecture Notes in Mathematics No. 642, Springer-Verlag, Berlin/Heidelberg/New York, 1978; and in “Proceedings of the April 1978 Meeting of the New York Academy of Sciences”] that all Hadamard matrices of character 2 and order 24 have higher transpose character and that there is exactly one matrix of order 24 with both characters one.     

On the approximability of the Maximum Agreement SubTree and Maximum Compatible Tree problems

The aim of this paper is to give a complete picture of approximability for two tree consensus problems which are of particular interest in computational biology: Maximum Agreement SubTree (MAST) and Maximum Compatible Tree (MCT). Both problems take as input a label set and a collection of trees whose leaf sets are each bijectively labeled with the label set. Define the size of a tree as the number of its leaves. The well-known MAST problem consists of finding a maximum-sized tree that is topologically embedded in each input tree, under label-preserving embeddings. Its variant MCT is less stringent, as it allows the input trees to be arbitrarily refined. Our results are as follows. We show that MCT is -hard to approximate within bound n^1−? on rooted trees, where n denotes the size of each input tree; the same approximation lower bound was already known for MAST [J. Jansson, Consensus algorithms for trees and strings, Ph. D. Thesis, Lund University, 2003]. Furthermore, we prove that MCT on two rooted trees is not approximable within bound 2^log1−?n, unless all problems in are solvable in quasi-polynomial time; the same result was previously established for MAST on three rooted trees [J. Hein, T. Jiang, L. Wang, K. Zhang, On the complexity of comparing evolutionary trees, Discrete Applied Mathematics 71 (1-3) (1996) 153-169] (note that MAST on two trees is solvable in polynomial time [M.A. Steel, T.J. Warnow, Kaikoura tree theorems: Computing the maximum agreement subtree, Information Processing Letters 48 (2) (1993) 77-82]). Let CMAST, resp. CMCT, denote the complement version of MAST, resp. MCT: CMAST, resp. CMCT, consists of finding a tree that is a feasible solution of MAST, resp. MCT, and whose leaf label set excludes a smallest subset of the input labels. The approximation threshold for CMAST, resp. CMCT, on rooted trees is shown to be the same as the approximation threshold for CMAST, resp. CMCT, on unrooted trees; it was already known that both CMAST and CMCT are approximable within ratio three on rooted and unrooted trees [V. Berry, F. Nicolas, Maximum agreement and compatible supertrees, in: S.C. Sahinalp, S. Muthukrishnan, U. Dogrusoz (Eds.), Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM’04, in: LNCS, vol. 3109, Springer-Verlag, 2004, pp. 205-219; G. Ganapathy, T.J. Warnow, Approximating the complement of the maximum compatible subset of leaves of k trees, in: K. Jansen, S. Leonardi, V. V. Vazirani (Eds.), Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX’02, in: LNCS, vol. 2462, Springer-Verlag, 2002, pp. 122-134]. The latter results are completed by showing that CMAST is -hard on three rooted trees and that CMCT is -hard on two rooted trees.