|
In this area the research work at DIS in 1995 was carried on in the following directions:
In this area two research directions are pursued.
Along the first direction theoretical aspects of approximability have been studied. In particular a survey of the main research results in the characterization of approximable problems has been published [I2-5] and research on the class of problems that can be efficiently approximated by means of local search algorithms has been continued [I2-8, I2-9]. Besides, the study of more powerful local search approximation techniques, that generalize the standard technique and enlarge the power of this general paradigm, have been developed [I2-1].
Along the second line, approximation algorithms have been designed for specific combinatorial problems. Namely in [I2-2] local search approximate heuristics for several colorability problems for undirected and directed hypergraphs, that are generalization of many well known NP-hard optimization problems, such as Max Cut, Max Directed Cut, and Set Splitting, have been proposed.
Successively [I2-41] the minimum independent dominating set problem in bounded degree graphs has been studied, and approximate algorithms based on greedy and local search techniques has been developed.
In [I2-33, I2-40] the authors consider the problem of updating a single source shortest path tree in either a directed or an undirected graph, with positive real edge weights. The proposed semidynamic algorithms for the incremental problem (handling edge insertions and cost decrements) work for any graph, but their performances depend on the class of the considered graph. In any case the algorithms have optimal space requirements and query time. The cost of updates is computed in terms of amortized complexity and depends on the size of the output modifications. In the case of graphs with bounded genus, or bounded arboricity graphs, the incremental algorithm requires O(log n) amortized time per vertex update. For general graphs with n vertices and m edges our incremental solution requires O(m log n) amortized time per vertex update. The decremental problem for planar graphs is also considered, providing algorithms and data structures with analogous performances.
This approach is further extended in [I2-34] to deal with fully dynamic sequences of updates in general graphs. The cost of update operations depends on the class of the considered graph and on the number of vertices that, due to an edge modification, either change their distance from the source or change their parent in the shortest path tree. In the case of graphs with bounded genus (including planar graphs), bounded degree graphs, bounded treewidth graphs and B-near-planar graphs with bounded B, the update procedures require O(log n) amortized time per vertex update, while for general graphs with n vertices and m edges they require O(m log n) amortized time per vertex update. Experimental tests show considerable advantages of this approach over the basic Dijkstra's algorithm.
Average case analysis of dynamic algorithms for fully dynamic connectivity for directed graphs has been considered in [I2-4].
Dynamic algorithms for the on-line maintenance of weighted hypergraphs have been devised with application to satisfiability of propositional Horn formulae with uncertainty in [I2-7], where the authors show how to represent a significant class of formulae by weighted directed hypergraphs and present two algorithms that solve the on-line Horn-SAT problem and find a minimum model for the formula working on the dynamic weighted hypergraph representation. These algorithms make increasing assumptions on the formula and the second one solves the on-line Horn-SAT problem with a total time linear in the size of the formula, matching the optimal result for Boolean Horn formulae.
In [I2-42] algorithms for deciding properties of Petri nets that make use of an a hypergraph-based approach have been presented. Namely the proposed algorithms allow to decide liveness and boundedness of the net, and to dynamically maintain the set of potentially firabile transitions for conflict-free Petri nets and the wider classes of series-parallel-conflict-free and series-parallel- nondeterministic-conflict-free Petri nets.
The problem of automatically drawing a graph is a classical research theme. Dynamic graph drawing problems are studied in [I2-18, I2-24, I2-25] for planar graphs, trees and convex planar graphs. Combinatorial properties of triangular planar graphs are investigated in [I2-26]. Proximity problems are analyzed in [I2-23, I2-36]. Upward planarity testing for single source acyclic digraphs is studied in [I2-15]. Experimental studies comparing general-purpose graph drawing algorithms are carried out in [I2-21]. Other graph drawing issues are analyzed in [I2-14, I2-17, I2-22].
Regarding the study of algorithmic techniques for combinatorial problems, in [I2-45] a characterization of a DFS-forest on directed graphs is proposed in terms of a relaxed planar embedding of its structure. An algorithm, based on that characterization, is proposed in order to maintain a DFS-forest in a directed acyclic graph with n nodes and m edges, achieving O(nm) total time in the worst case for any sequence of arc insertions, that is O(n) amortized time per arc insertion in a sequence of m such operations. This favourably compares with the time required to recompute DFS from scratch by using Tarjan's O(n+m) algorithm. Although this problem was pointed out almost a decade ago, this is the first algorithm for dynamic DFS for nontrivial classes of graphs.
A topological order of the vertices of a directed acyclic graph G=(V, E) is any total order ORD such that if (x, y) is in E, then x precedes y in ORD. In [I2-46] the authors consider the dynamic version of this problem, and provide simple algorithms and data structures achieving O(n) amortized time per edge insertion starting from an empty graph, which favourably compares to the trivial O(m+n) time bound per operation obtained applying the off-line algorithm. The additional space requirement, beside the representation of the graph itself, is O(n). Experimental results show that our algorithm performs in practice orders of magnitude faster than the off-line algorithm.
In [I2-39] an implicit data structure for partial lattice representation is presented, which allows to test partial order relation among two given elements in constant time. The data structure proposed has an overall O(n sqrt(n))-space complexity, where n is the element set size. This data structure is extended in [I2-47] for supporting new operations.
The hive graph is a rectangular graph, introduced by Chazelle, satisfying some additional condition widely used in computational geometry for solving several kinds of fundamental queries. In [I2-19] an algorithm for incrementally building a hive graph structure is given; while it retains the same optimal performance in query answering, it also allows to incrementally insert new line segments optimal time. A temporal database application of our results is given.
In [I2-13] the authors face the problem of computing an enclosing pair of axis-parallel rectangles of a set of polygonal objects in the plane, serving as a simple container.
In [I2-43] it is shown that bounded spherical orders, i.e. orders with a single minimum and a single maximum and whose Hasse diagram h as a crossing free upward drawing on a sphere, have Boolean dimension never greater than 4, and not greater than 5 in the case the poset has more than one maximal element, but only one minimum. These results are obtained by a characterization of spherical orders in terms of containment between circular arcs. Since the transitive closure of a directed acyclic graph is always described by a partial order, this result gives a constant time reachability testing algorithm for an extension of the class of s-t dags.
The method proposed in [I2-35] can also be used to optimally solve the multiprocessor scheduling problem where jobs have different completion times on different processors. The other setting, where jobs have the same completion time on all processors, is studied in [I2-12] with the additional constraint that each job can be either accepted or rejected at the expense of some penalty; Optimal algorithms are given when the goal is to minimize the maximal completion time of accepted jobs plus the total penalty for rejected jobs.
In [I2-10] the problem of deciding when to invest capital to buy new machinery that allows to produce with less cost is studied. Here the goal is to minimize the global production cost and the capital investments used to improve the production.
In [I2-6] the problem of scheduling a server in a metric space as to cover a set of requests given in on- line fashion has been considered, with the constraint that the server has to return to the origin when the sequence of requests terminates. For sake of intuition the problem has been called On-line Travelling Salesman Problem. Competitive algorithms that update efficiently the route of the server when new requests are presented have been proposed for various metric spaces and more powerful specific results have been achieved in the case of the real line.
The problem of scheduling broadcast transmissions in packet radio networks using a TDMA (Time Division Multiple Access) protocol has been shown in [I2-16] to be intractable. Furthermore distributed algorithms are proposed which has been sperimentally tested as giving near-optimal solutions.
Several methods exist for routing messages in a network without using complete routing tables (compact routing). In k-interval routing schemes (k-IRS), links carry up to k intervals each. A message is routed over certain link if its destination belongs to one of the intervals of the link. In [I2-32] some results for the necessary value of k in order to achieve shortest path routing are given. Even though for very structured networks low values of k suffice, it is shown that for 'general graphs' interval routing cannot significantly reduce the space-requirements for shortest path routing. In [I2-30] an extension of the Interval Routing Scheme k-IRS to the multi-dimensional case kd is introduced.
In [I2-27] the attention is focused on deadlock avoidance methods for routing messages in parallel and distributed networks. In particular, the concept of systolic acyclic orientation is introduced.
In [I2-44] the computational complexity of finding (off and on-line) minimum packet routing schemes is studied, both in terms of end-to-end delay and of completion time. In particular the authors first show that, in both cases, it is not possible to find optimal schemes and, then prove the hardness of approximating the minimum end-to-end delay in polynomial time. Next, it is shown that polynomial time approximation schemes (PTAS) cannot exist for the minimum completion time problem, and some approximation algorithms are given.
In this area the distributed computation in totally synchronous distributed network is also studied; that is synchronous system for which the simmetry breaking problem is unsolvable, and then it is not possible to elect a leader and centralize the computation. In [I2-3] the problem of finding the extrema in a distributed multiset is considered, that is of determining the minimum and the maximum value of a multiset whose elements are drawn from a totally ordered universe and stored at the entity of a ring network.
In [I2-28] the authors investigate the existence of efficient algorithms to arbitrate access of clients in a distributed network to a shared resource by using a token-passing strategy. In particular the setting is considered where network topology is a one-directional ring and requests are anonymous.
Due both to the well established quality of the research and to the participation to international projects the scientific cooperation in this area has been very active both at national level (University of L'Aquila, University of Rome "Tor Vergata," University of Salerno, IASI-CNR, etc.) and at international level. Perticularly relevant have been the scientific relationships with INRIA (Paris), Charles University (Prague), University of Utrecht, Columbia University, Brown University, University of Maryland, IBM T. J. Watson Research Center, International Computer Science Institute (Berkeley), ETH (Zurich), Tel-Aviv University, INRIA (Sophia Antipolis), Mc Gill University (Canada), Paderborn University (Germany), Carleton University (Canada).
[I2-2] P. Alimonti, Non-Oblivious Local Search for Graph and Hypergraph Coloring Problems, Proc. of 21st International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 1017, Springer Verlag, 1995.
[I2-3] P. Alimonti, P. Flocchini, N. Santoro, Finding the Extrema in a Distributed Multiset, Journal of Parallel and Distributed Computing (to appear).
[I2-4] P. Alimonti, S. Leonardi, A. Marchetti Spaccamela, Average Case Analysis of Fully Dynamic Connectivity for Directed Graphs, RAIRO Journal on Theoretical Informatics and Applications (to appear).
[I2-5] G. Ausiello, P. L. Crescenzi, M. Protasi, Approximate solution of NP optimization problems, J. of Theoretical Computer Science, 150 (1995) 1-55.
[I2-6] G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie and M. Talamo. Competitive algorithms for the on-line traveling-salesman. Proceedings of the 4th Workshop on Algorithms and Data Structures (WADS 95), Lecture Notes in Computer Science 955, Springer-Verlag, 1995, pp. 206-217.
[I2-7] G. Ausiello, R. Giaccio, On-line algorithms for satisfiabillity problems with uncertainty, Theoretical Computer Science (to appear).
[I2-8] G. Ausiello, M. Protasi, NP Optimization Problems and Local Optima, Graph Theory, Combinatorics and Applications: Proc. of the Seventh Quadr. Int. Conf. on the Theory and Applications of Graphs, 2nd Vol., Y. Alavi and A. Schwenk Eds., 957-975, Wiley and Sons, Inc. 1995.
[I2-9] G. Ausiello, M. Protasi, Local search, reducibility and approximability of NP optimization problems, Information Processing Letters, 54 (1995) 73-79.
[I2-10] Y. Azar, Y. Bartal, E. Feuerstein, A. Fiat, S. Leonardi and A. RosÈn. On capital investment. Proceedings of the 23rd International Colloquium on Automata, Languages, and Programming (ICALP 96), 1996.
[I2-11] Y. Bartal, A. Fiat and S. Leonardi. Lower bounds for on-line graph problems with application to on-line circuit and optical routing. Proceedings 28th ACM Symposium on Theory of Computing (STOC 96), 1996.
[I2-12] Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, L. Stougie and J. Sgall. Multiprocessor scheduling with rejection. Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 96).
[I2-13] B. Becker, P. G. Franciosa, S. Gschwind, S. Leonardi, T. Ohler and P. Widmayer. Enclosing a set of objects by two minimum area rectangles. To appear in Journal of Algorithms.
[I2-14] P. Bertolazzi, G. Di Battista, G. Liotta, Parametric Graph Drawing, IEEE Trans. on Software Engineering, vol.SE-21, no.8, pp.662-673, 1995.
[I2-15] P. Bertolazzi, G. Di Battista, C. Mannino, R. Tamassia, Optimal Upward Planarity Testing for Single Source Acyclic Digraphs, to appear in SIAM Journal on Computing, 1996.
[I2-16] M. A. Bonuccelli and S. Leonardi. On scheduling variable length broadcasts in packet radio networks. To appear in Telecommunication Systems, special issue on Satellite Communication Systems and Networks.
[I2-17] L. Buti, G. Di Battista, G. Liotta, E. Tassinari, F. Vargiu, L. Vismara, Graph Drawing Workbench in Graph Drawing (Proc. Int. Workshop on Graph Drawing, Passau, Germany, September 20 - 22, 1995), F.Brandemburg (ed.), Lecture Notes in Computer Science, Springer Verlag, pp.111-122, 1995.
[I2-18] R. F. Cohen, G. Di Battista, R. Tamassia, I. G. Tollis, Dynamic Graph Drawing: Trees, Series-Parallel Graphs, and Planar st-Digraphs, SIAM Journal on Computing, vol.24, no.5, pp.970-1001, 1995.
[I2-19] F. d'Amore and R. Giaccio, Incremental hive graph, Proc. of 21st Internat. Workshop Graph- Theoretic Concepts Comput. Sci. (WG '95), Lecture Notes in Computer Science, Springer- Verlag, vol. 1017, jun 1995, pp. 49-61.
[I2-20] F. d'Amore and V. H. Nguyen and T. Roos and P. Widmayer, On Optimal Cuts of Hyperrectangles, Computing, Springer-Verlag, vol. 55, 1995, pages 191-206.
[I2-21] G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, F. Vargiu, An Experimental Comparison of Three Graph Drawing Algorithms, to appear in Proc.11th Annual ACM Symposium on Computational Geometry, Vancouver, Canada, June 5-7 1995.
[I2-22] G. Di Battista, G. Liotta, F. Vargiu, Diagram Server, Journal of Visual Languages and Computing, vol.6, no.3, pp.275-298, 1995.
[I2-23] G. Di Battista, G. Liotta, S. Whitesides, The Strength of Weak Proximity in Graph Drawing (Proc. Int. Workshop on Graph Drawing, Passau, Germany, September 20 - 22, 1995), F.Brandemburg (ed.), Lecture Notes in Computer Science, Springer Verlag, pp.178-189, 1995.
[I2-24] G. Di Battista, R. Tamassia, On-Line Planarity Testing, to appear in SIAM Journal on Computing, 1996.
[I2-25] G. Di Battista, R. Tamassia, On-line Maintenance of Triconnected Components with SPQR Trees, to appear in Algorithmica, 1996.
[I2-26] G. Di Battista, L. Vismara, Angles of Planar Triangular Graphs, to appear in SIAM Journal on Discrete Mathematics, 1996.
[I2-27] M. Di Ianni, M. Flammini, R. Flammini, S. Salomone, Systolic Acyclic Orientations for Deadlock Prevention, Proc. of 2nd Colloquium on Structural Information and Communication Complexity (SIROCCO), Carleton University Press, 1995.
[I2-28] E. Feuerstein, S. Leonardi, A. Marchetti-Spaccamela and N. Santoro. Efficient token-based control in rings. To appear as brief announcement in Proceedings of the 15th ACM Symposium on Principles of Distributed Computing (PODC 96), 1996.
[I2-29] M. Flammini, G. Gambosi, S. Salomone, Interval Routing Schemes, Algorithmica (to appear).
[I2-30] M. Flammini, G. Gambosi, U. Nanni, R. B. Tan, Multi-dimensional Interval Routing Schemes, Proc. of 9th Int. Workshop on Distributed Algorithms (WDAG), Lecture Notes in Computer Science 972, Springer-Verlag, 1995.
[I2-31] M. Flammini, G. Gambosi, S. Salomone, On Devising Boolean Routing Schemes, Proc. of 21st Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG), Lecture Notes in Computer Science, Springer-Verlag, 1995.
[I2-32] M. Flammini, A. Marchetti Spaccamela, J. van Leeuwen, The Complexity of Interval Routing on Random Graphs, Proceedings of 20th Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science 969, Springer-Verlag, 1995.
[I2-33] D. Frigioni, A. Marchetti-Spaccamela, U. Nanni, Semi-dynamic Algorithms for Maintaining Single-Source Shortest Path Trees, Algorithmica - Special Issue on Dynamic Graph Algorithms, to appear.
[I2-34] D. Frigioni, A. Marchetti-Spaccamela, U. Nanni, Fully Dynamic Output Bounded Single Source Shortest Path Problem, Accepted for presentation at the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA 96).
[I2-35] S. Leonardi and A. Marchetti-Spaccamela. On-line resource management with applications to routing and scheduling. Proceedings of the 22nd International Colloquium on Automata, Languages and Programming (ICALP 95), Lecture Notes in Computer Science 944, Springer- Verlag, 1995, pp. 303-314.
[I2-36] G. Liotta, G. Di Battista, Proximity Drawing of Trees in the 3-D Space, Proc. 4th Workshop on Algorithms and Data Structures, Kingston, Canada, August 1995, S.G.Akl, F.Dehne, J.Sack, N.Santoro (eds.), Lecture Notes in Computer Science, Springer Verlag, pp.239-250, 1995.
[I2-37] P. Reverberi, M. Talamo, A theoretical approach to diagnostic problem-solving in Bayesian belief networks, Proceedings of the UNICOM International Conference on Applied Decision Technologies - Probabilistic Reasoning and Computational Learning Session, London, 1995, pp. 185-207.
[I2-38] P. Reverberi, M. Talamo, Modelling interactive decision-making in Bayesian belief networks, accepted at the 17th International Conference on System Modelling and Optimization, Prague.
[I2-39] M. Talamo, P. Vocca, Fast Lattice Browsing on a Sparse Representation, To appear in TCS.
[I2-42] P. Alimonti, E. Feuerstein, U. Nanni, Linear Time Algorithms for Liveness and Boundedness for Conflict-Free Petri Nets and Generalization, submitted to Theoretical computer Science.
[I2-43] G. Brightwell, P. G. Franciosa, On the Boolean dimension of spherical orders, Tech.Rep. London School of Economics, Mathematical Preprint Series LSE-MPS-93, November 1995. Submitted to Orders.
[I2-44] M. Di Ianni, M. Flammini, On the efficient off-line and on-line packet routing, Rapporto Tecnico del Dip. di Matematica Pura ed Appl. della Universitý degli Studi di L'Aquila, n.84, 1995, and Tech. Rep. of the CEE Research Project ìESPRIT II Research Action Program under contract N.8141 - Algorithms and Complexity II (ALCOM II)î, 1995, submitted.
[I2-45] P. G. Franciosa, G. Gambosi and U. Nanni, The incremental maintenance of a Depth-First- Search Tree in directed aciclic graphs, Submitted for pubblication.
[I2-46] A. Marchetti-Spaccamela, U. Nanni, H. Rohnert, Maintaining On-line a Topological Order, Submitted for pubblication.
[I2-47] M. Talamo, P. Vocca, A Time Optimal O(n sqrt(n))-Space Data Structure for Lattice Representation. Submitted to SIAM Journal on Comp.
|
|
Go back to the Home Page of Algorithm Engineering. |
|
Go back to the Home Page of Dipartimento di Informatica e Sistemistica. | |
|
|
For problems or comments about this page, please send email to ae@dis.uniroma1.it. |
|
Search pages of Algorithm Engineering. |