Title Algorithms and complexity : 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings / edited by Dimitris Fotakis, Aris Pagourtzis, Vangelis Th. Paschos

Published Cham : Springer, 2017

Click on the following:
Springer eBooks

Copies

Description 1 online resource (XX, 486 pages) : illustrations Series Lecture Notes in Computer Science, 0302-9743 ; 10236 Lecture notes in computer science ; 10236. 0302-9743 Contents Intro -- Preface -- Organization -- Invited Talks -- TFNP: An Update -- 2-Edge and 2-Vertex Connectivity in Directed Graphs -- New Algorithmic Results for Bin Packing and Scheduling -- Contents -- Extended Abstracts -- TFNP: An Update -- 1 Introduction -- 2 Recent Developments -- 3 Open Problems -- References -- New Algorithmic Results for Bin Packing and Scheduling -- 1 Introduction -- 2 Scheduling Problems -- 2.1 Known Results -- 2.2 New Results -- 3 Bin Packing -- 3.1 Known Results -- 3.2 New Results -- References -- Regular Papers -- Scheduling Maintenance Jobs in Networks 1 Introduction -- 2 Preemptive Scheduling -- 3 Non-preemptive Scheduling -- 4 Power of Preemption -- 5 Mixed Scheduling -- 6 Conclusion -- References -- Paths to Trees and Cacti -- 1 Introduction -- 2 Preliminaries -- 3 Kernel for Bounded Out-Tree Contraction -- 4 Kernel Lower Bounds -- 4.1 Lower bound for Bounded OTC -- References -- Temporal Flows in Temporal Networks -- 1 Introduction and Motivation -- 1.1 Our Model, the Problem, and Our Results -- 1.2 Previous Work -- 1.3 Formal Definitions -- 2 LP for the MTF Problem with or Without Bounded Buffers 3 Temporal Networks with Unbounded Buffers at Nodes -- 3.1 Basic Remarks -- 3.2 The Time-Extended Flow Network and Its Simplification -- 4 Mixed Temporal Networks and Their Hardness -- 4.1 Temporal Networks with Random Availabilities that are Flow Cutters -- 4.2 The Complexity of Computing the Expected Maximum Temporal Flow -- References -- Completeness Results for Counting Problems with Easy Decision -- 1 Introduction -- 1.1 Related Work -- 2 Preliminaries -- 3 #Monotone-Circuit-Sat is TotP -complete Under Karp Reductions -- 3.1 #Monotone-Circuit-Sat is TotP -hard 3.2 #Monotone-Circuit-Sat Is in TotP -- 4 More TotP -complete Problems -- 5 Discussion on Approximability Implications -- 6 Conclusion and Open Problems -- References -- Tracking Paths -- 1 Introduction -- 2 Hardness Results -- 3 Tracking Paths in Planar Graphs -- 4 Catching the Intruder -- References -- On the Complexity of Finding a Potential Community -- 1 Introduction -- 2 Preliminaries -- 3 Complexity Jump from Planar Graphs to Apex Graphs -- 4 Graph Classes with Polynomial-Time Algorithms -- 5 NP-hardness and Non-approximability -- 6 Conclusion -- References Improved Lower Bounds for Graph Embedding Problems -- 1 Introduction -- 2 Preliminaries -- 3 String Crafting and Orthogonal Vector Crafting -- 4 Lower Bounds for Graph Embedding Problems -- 5 Tree and Path Decompositions with Few Bags -- 6 Intervalizing Coloured Graphs -- 7 Conclusions -- References -- Collaboration Without Communication: Evacuating Two Robots from a Disk -- 1 Introduction -- 1.1 Related Work -- 1.2 Model -- 1.3 Notation -- 2 Determining the Worst-Case Placement of the Exit -- 3 Evacuating from a Disk -- 3.1 The Algorithm A(y, d) Summary This book constitutes the refereed conference proceedings of the 10th International Conference on Algorithms and Complexity, CIAC 2017, held in Athens, Greece, in May 2017. The 36 revised full papers were carefully reviewed and selected from 90 submissions and are presented together with 3 abstracts of invited talks and a paper to the 70th birthday of Stathis Zachos. The papers present original research in the theory and applications of algorithms and computational complexity Bibliography Includes bibliographical references and author index Subject Computer algorithms -- Congresses Computational complexity -- Congresses Discrete mathematics. Algorithms & data structures. Computers -- Data Processing. Computers -- Data Modeling & Design. Computers -- Programming -- Algorithms. Computer algorithms Computational complexity Data structures (Computer science) Algorithms Computer science Computer science -- Mathematics Genre/Form proceedings (reports) Conference papers and proceedings Conference papers and proceedings. Actes de congrès. Form Electronic book Author Fotakis, Dimitris, editor Pagourtzis, Aris, editor Paschos, Vangelis Th, editor ISBN 9783319575865 3319575864

  Permalink