Computing and software science : state of the art and perspectives / Bernhard Steffen, Gerhard Woeginger (eds.).

Includes bibliographical references and author index.

Online resource; title from PDF title page (SpringerLink, viewed October 9, 2019).

Intro; Geleitwort; References; Preface; Organization; Contents; Computation and Complexity; Computation and Complexity; References; Some Estimated Likelihoods for Computational Complexity; 1 Introduction; 1.1 Some Estimated Likelihoods for Some Major Open Problems; 2 Thoughts on Various Separations; 2.1 EXP with an NP Oracle Versus BPP; 2.2 NEXP vs P/poly; 2.3 LOGSPACE vs NP; 2.4 NP Does Not Have Fixed Polynomial-Size Circuits; 2.5 BPP is in Sub-Exponential Time; 2.6 P vs PSPACE; 2.7 P vs NP; 2.8 ETH: The Exponential Time Hypothesis; 2.9 NC1 versus TC0; 2.10 EXP vs NEXP

2.11 SETH: The Strong Exponential Time Hypothesis2.12 NEXP vs CoNEXP; 2.13 NSETH: Nondeterministic SETH; 2.14 L vs RL; References; Computing in Combinatorial Optimization; 1 In the Beginning was n Factorial; 2 Dantzig, Linear Programming, and Cutting Planes; 3 Edmonds, Matchings, and Polynomial Time; 4 Sixty-Three Years of Progress; 5 Wish List of Research Directions; 5.1 Improving the Simplex Method; 5.2 Language of Algorithms; 5.3 Understanding Heuristic Algorithms; 5.4 Analysis of Exact Algorithms for Hard Problems; 5.5 Complexity of Cutting-Plane Methods; References

Computational Social Choice: The First Ten Years and Beyond1 Introduction; 2 Restricted Preference Domains; 3 Voting Equilibria and Iterative Voting; 4 Multiwinner Voting; 5 Probabilistic Social Choice; 6 Random Assignment; 7 Computer-Aided Theorem Proving; 8 Further Reading; References; Geometric Optimization Revisited; 1 Introduction; 2 Geometric Set Cover; 2.1 Greedy Algorithms; 2.2 Iterative Reweighing Scheme and -Nets; 2.3 Extensions; 3 Geometric Independent Set; 4 Maps Between Point Sets; 4.1 Transportation Maps; 4.2 Order Preserving Maps; 4.3 Extensions; 5 Discussion; References

10 Reasons to Get Interested in Graph Drawing1 Introduction; 2 Basic Research; 2.1 Computational Geometry; 2.2 Graph Theory: Canonical Orderings; 2.3 Complexity: A Real Analogue of NP in Graph Drawing; 2.4 Data Structures: SPQR-Tree; 3 Applications; 3.1 Information Visualization; 3.2 Software Engineering; 3.3 Model-Based Design; 3.4 Automated Cartography; 3.5 Social Sciences; 3.6 Molecular Biology; References; Sublinear-Time Algorithms for Approximating Graph Parameters; 1 Introduction; 1.1 Average Degree and Higher Moments of the Degree Distribution; 1.2 The Number of Connected Components

1.3 Minimum Vertex Cover and Related Parameters1.4 Minimum Weight Spanning Tree; 1.5 Distance to Properties; 1.6 Organization; 2 Preliminaries; 3 Moments of the Degree Distribution; 3.1 Average Degree; 3.2 Higher Moments; 4 Minimum Vertex Cover and Maximum Matching; 4.1 Building on a Distributed Algorithm; 4.2 Building on a Random Ordering; 5 Minimum Weight Spanning Tree; References; Dynamic Erdős-Rényi Graphs; 1 Introduction; 2 Erdős-Rényi Graphs Under Regime Switching; 2.1 Generating Function; 2.2 Moments; 2.3 Diffusion Results Under Scaling; 2.4 Large Deviations Results Under Scaling

The papers of this volume focus on the foundational aspects of computer science, the thematic origin and stronghold of LNCS, under the title "Computing and Software Science: State of the Art and Perspectives". They are organized in two parts: The first part, Computation and Complexity, presents a collection of expository papers on fashionable themes in algorithmics, optimization, and complexity. The second part, Methods, Languages and Tools for Future System Development, aims at sketching the methodological evolution that helps guaranteeing that future systems meet their increasingly critical requirements. -- Provided by publisher