Algorithms and complexity : 6th Italian conference, CIAC 2006, Rome, Italy, May 29-31, 2006 : proceedings / / Tiziana Calamoneri, Irene Finocchi, Giuseppe F. Italiano (eds.)

• Pubblicazione: Berlin, : Springer, 2006
• Edizione: 1st ed. 2006.
• Descrizione fisica: 1 online resource (XII, 396 p.)
• Disciplina: 511.8
• Soggetto topico: Algorithms; Computational complexity
• Altri autori: CalamoneriTiziana FinocchiIrene ItalianoGiuseppe F
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di bibliografia: Includes bibliographical references and index.
• Nota di contenuto: Invited Talks -- Reliable and Efficient Geometric Computing -- Beware of the Model: Reflections on Algorithmic Research -- On Search Problems in Complexity Theory and in Logic (Abstract) -- Session 1 -- Covering a Set of Points with a Minimum Number of Lines -- Approximation Algorithms for Capacitated Rectangle Stabbing -- In-Place Randomized Slope Selection -- Session 2 -- Quadratic Programming and Combinatorial Minimum Weight Product Problems -- Counting All Solutions of Minimum Weight Exact Satisfiability -- Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms -- Session 3 -- Network Discovery and Verification with Distance Queries -- Deciding the FIFO Stability of Networks in Polynomial Time -- Heterogenous Networks Can Be Unstable at Arbitrarily Low Injection Rates -- Session 4 -- Provisioning a Virtual Private Network Under the Presence of Non-communicating Groups -- Gathering Algorithms on Paths Under Interference Constraints -- On the Hardness of Range Assignment Problems -- Session 5 -- Black Hole Search in Asynchronous Rings Using Tokens -- On Broadcast Scheduling with Limited Energy -- A Near Optimal Scheduler for On-Demand Data Broadcasts -- Session 6 -- Fair Cost-Sharing Methods for Scheduling Jobs on Parallel Machines -- Tighter Approximation Bounds for LPT Scheduling in Two Special Cases -- Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations -- Session 7 -- Approximate Hierarchical Facility Location and Applications to the Shallow Steiner Tree and Range Assignment Problems -- An Approximation Algorithm for a Bottleneck Traveling Salesman Problem -- On the Minimum Common Integer Partition Problem -- Session 8 -- Matching Subsequences in Trees -- Distance Approximating Trees: Complexity and Algorithms -- How to Pack Directed Acyclic Graphs into Small Blocks -- Session 9 -- On-Line Coloring of H-Free Bipartite Graphs -- Distributed Approximation Algorithms for Planar Graphs -- A New NC-Algorithm for Finding a Perfect Matching in d-Regular Bipartite Graphs When d Is Small -- Session 10 -- Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments -- Parameterized Algorithms for Hitting Set: The Weighted Case -- Fixed-Parameter Tractable Generalizations of Cluster Editing -- Session 11 -- The Linear Arrangement Problem Parameterized Above Guaranteed Value -- Universal Relations and #P-Completeness -- Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes.
• Sommario/riassunto: Here are the refereed proceedings of the 6th Italian Conference on Algorithms and Computation, CIAC 2006. The 33 revised full papers presented together with 3 invited papers address such topics as sequential, parallel and distributed algorithms, data structures, approximation algorithms, randomized algorithms, on-line algorithms, graph algorithms, analysis of algorithms, algorithm engineering, algorithmic game theory, computational biology, computational complexity, communication networks, computational geometry, cryptography, discrete optimization, graph drawing, mathematical programming, and quantum algorithms.
• Altri titoli varianti: CIAC 2006
• Titolo autorizzato: Algorithms and complexity
• ISBN: 3-540-34378-4
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910484986403321
• Lo trovi qui: Univ. Federico II
• Serie: Lecture notes in computer science ; ; 3998.; LNCS sublibrary. : SL 1, . -Theoretical computer science and general issues.