| Description |
1 online resource (xix, 395 pages) : illustrations |
| Series |
Lecture notes in computer science, 0302-9743 ; 9210 |
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 9210. 0302-9743
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| Contents |
880-01 Intro; Preface; Conference Organization; Invited Talks; It is Better to be Vaguely Right Than Exactly Wrong; Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies; On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS; Contents; Invited talks; Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies; 1 Introduction; 2 Underlying Idea; 3 TSP and Related Problems; 4 Bounded Occurrence Optimization Problems; 5 Bi-wheel Amplifier Graphs; 6 Preparation Lemma; 7 Instances of Metric TSP |
|
880-01/(S 3.1 Number of Different Stabbing 3-Rectangles3.2 Algorithm; 4 Stabbing Rectangles; References; β-skeletons for a Set of Line Segments in R2; 1 Introduction; 2 Preliminaries; 3 Algorithm for Computing β-skeletons for 0 <β <1; 4 Finding β-skeletons for 1 ≤ β; 5 Computing Gabriel Graph for Segments; 6 Conclusions; References; Complexity and Boolean Functions; Depth, Highness and DNR Degrees; 1 Introduction; 2 Preliminaries; 3 C-Depth; 3.1 MLR is not Order-deepC; 3.2 The SGL Fails for C-depth; 3.3 Depth Implies Highness or DNR; 4 K-Depth; 4.1 Highness and Depth Coincide |
|
8 Instances of Asymmetric TSP (ATSP)9 A Role of Weights; 10 Graphic TSP; 11 Some Applications; 12 Summary of Main Results; 13 Further Research; References; On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS; 1 Introduction; 2 Preliminaries; 2.1 Probabilistic Vector Addition Systems with States; 2.2 Patterns and Pattern Frequencies; 3 Pattern Frequency in One-Counter pVASS; 3.1 Approximating [p↓q] and [p↑]; 3.2 Approximating E R↓s and E#t r↓s; 4 Pattern Frequency in Two-Counter pVASS; 5 Future Research; References; Geometry, Combinatorics, Text Algorithms |
|
Longest -Gapped Repeat and Palindrome1 Introduction; 2 Preliminaries; 3 Our Solution; References; On the Enumeration of Permutominoes; 1 Introduction; 2 Preliminaries; 3 The Inflate-Paste Technique; 4 Direct Enumeration of Permutominoes; 5 Tailoring the Algorithm to Specific Subclasses; 5.1 Convex Permutominoes; 5.2 Row-Convex Permutominoes; 6 Conclusion; References; Stabbing Segments with Rectilinear Objects; 1 Introduction; 2 Stabbing with One or Two Halfplanes; 2.1 Stabbing Halfplane; 2.2 Stabbing Strips; 2.3 Stabbing Quadrants; 3 Stabbing with Three Halfplanes |
|
4.2 Depth Implies Highness or DNR4.3 A Low Deep Set; 4.4 No K-Trivial is O(1)-deepK; 5 Infinitely Often Depth and Conditional Depth; 6 Conclusion; References; On the Expressive Power of Read-Once Determinants; 1 Introduction; 2 Basic Observations; 3 Elementary Symmetric Polynomials and Permanent; 3.1 Elementary Symmetric Polynomials; 3.2 Non-expressibility of Permanent as ROD; 4 Non-expressible Monomial Sets; 5 Discussion and Open Problems; References; Constructive Relationships Between Algebraic Thickness and Normality; 1 Introduction and Known Results; 2 Preliminaries and Known Results |
| Summary |
This book constitutes the refereed proceedings of the 20th International Symposium on Fundamentals of Computation Theory, FCT 2015, held in Gda¿ℓsk, Poland, in August 2015. The 27 revised full papers presented were carefully reviewed and selected from 60 submissions. The papers cover topics in three main areas: algorithms, formal methods, and emerging fields and are organized in topical sections on geometry, combinatorics, text algorithms; complexity and Boolean functions; languages; set algorithms, covering, and traversal; graph algorithms and networking applications; anonymity and indistinguishability; graphs, automata, and dynamics; and logic and games |
| Analysis |
computerwetenschappen |
|
computer sciences |
|
wiskunde |
|
mathematics |
|
algoritmen |
|
algorithms |
|
computeranalyse |
|
computer analysis |
|
computernetwerken |
|
computer networks |
|
software engineering |
|
Information and Communication Technology (General) |
|
Informatie- en communicatietechnologie (algemeen) |
| Notes |
International conference proceedings |
|
Includes author index |
|
Online resource; title from PDF title page (SpringerLink, viewed August 14, 2015) |
| Subject |
Computer science -- Congresses
|
|
Network hardware.
|
|
Computer programming -- software development.
|
|
Discrete mathematics.
|
|
Software Engineering.
|
|
Algorithms & data structures.
|
|
Computers -- Hardware -- Network Hardware.
|
|
Computers -- Programming -- General.
|
|
Computers -- Data Processing.
|
|
Computers -- Software Development & Engineering -- General.
|
|
Computers -- Programming -- Algorithms.
|
|
Computer science
|
| Genre/Form |
Conference papers and proceedings
|
| Form |
Electronic book
|
| Author |
Kosowski, Adrian, editor.
|
|
Walukiewicz, Igor, editor.
|
| ISBN |
9783319221779 |
|
3319221779 |
|
3319221760 |
|
9783319221762 |
|
