Computing and software science : state of the art and perspectives /: state of the art and perspectives. (2019)

• Record Type: Book
• Further Information: Note: Bernhard Steffen, Gerhard Woeginger (eds.).
• Editors: Steffen, Bernhard; Woeginger, Gerhard
• Contents: 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
• Publisher Details: Cham, Switzerland : Springer
• Publication Date: 2019
• Extent: 1 online resource (xix, 590 pages), illustrations (some color)
• Subjects: 004; Computer science; Software engineering; Electronic books; Electronic books
• Languages: English
• ISBNs: 9783319919089; 3319919083
• Related ISBNs: 9783319919072
• Notes: Note: Includes bibliographical references and author index.; Note: Online resource; title from PDF title page (SpringerLink, viewed October 9, 2019).
• Access Rights: Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
• Access Usage: Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.