Algorithms and Complexity
Springer Berlin (Verlag)
978-3-540-34375-2 (ISBN)
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 PackDirected 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.
| Erscheint lt. Verlag | 16.5.2006 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science | Theoretical Computer Science and General Issues |
| Zusatzinfo | XII, 396 p. |
| Verlagsort | Berlin |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 576 g |
| Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
| Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik | |
| Schlagworte | algorithm • Algorithm analysis and problem complexity • algorithms • Approximation • combinatorial optimization • combinatorics • Complexity • Computational Geometry • Computational Graph Theory • data structure • data structures • Game Theory • geometric algorithms • Graph Algorithms • Graph Computations • network algorithms • Optimization • programming • Routing • Scheduling |
| ISBN-10 | 3-540-34375-X / 354034375X |
| ISBN-13 | 978-3-540-34375-2 / 9783540343752 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
