05272nam 22007575 450 99646590240331620230406054313.03-540-34378-410.1007/11758471(CKB)1000000000232983(SSID)ssj0000316176(PQKBManifestationID)11238997(PQKBTitleCode)TC0000316176(PQKBWorkID)10274783(PQKB)10442046(DE-He213)978-3-540-34378-3(MiAaPQ)EBC3068070(PPN)123135028(EXLCZ)99100000000023298320101221d2006 u| 0engurnn|008mamaatxtccrAlgorithms and Complexity[electronic resource] 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings /edited by Tiziana Calamoneri, Irene Finocchi, Guiseppe F. Italiano1st ed. 2006.Berlin, Heidelberg :Springer Berlin Heidelberg :Imprint: Springer,2006.1 online resource (XII, 396 p.) Theoretical Computer Science and General Issues,2512-2029 ;3998Bibliographic Level Mode of Issuance: Monograph3-540-34375-X Includes bibliographical references and index.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.Theoretical Computer Science and General Issues,2512-2029 ;3998AlgorithmsArtificial intelligence—Data processingComputer scienceComputer science—MathematicsDiscrete mathematicsComputer graphicsAlgorithmsData ScienceTheory of ComputationDiscrete Mathematics in Computer ScienceComputer GraphicsAlgorithms.Artificial intelligence—Data processing.Computer science.Computer science—Mathematics.Discrete mathematics.Computer graphics.Algorithms.Data Science.Theory of Computation.Discrete Mathematics in Computer Science.Computer Graphics.511.8Calamoneri Tizianaedthttp://id.loc.gov/vocabulary/relators/edtFinocchi Ireneedthttp://id.loc.gov/vocabulary/relators/edtItaliano Guiseppe Fedthttp://id.loc.gov/vocabulary/relators/edtItalian Conference on Algorithms and ComplexityBOOK996465902403316Algorithms and complexity55800UNISA