| Description |
1 online resource (xxxii, 335 pages) : illustrations |
| Series |
Lecture notes in computer science, 0302-9743 ; 10846 |
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 10846. 0302-9743
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| Contents |
Intro -- Preface -- Organization -- Abstract of Invited Talks -- Constructive and Non-constructive Combinatorics -- Physarum Solves Non-negative Undirected Linear Programs -- Limitations of Algebraic Lower Bound Proofs -- Complexity of Generation -- Lower Bounds for Unrestricted Boolean Circuits: Open Problems -- Online Labeling: Algorithms, Lower Bounds and Open Questions -- Reading MCSP Through SAT -- Recent Developments on the Asymmetric Traveling Salesman Problem -- Contents -- Complexity of Generation -- 1 How They Measure Complexity of Generation -- 2 Hard Generation Problems |
|
2.1 Examples -- 2.2 Circulation Cones and Polyhedra of Digrahs -- 2.3 Verifying Boolean Equalities and Inequalities -- 2.4 Sausage Lemma -- 2.5 A Sketch of the Proof of Theorem 1 for Digraphs -- 3 Flash-Light and Supergraph -- 4 Generating Dual-Bounded Hypergraphs -- 4.1 Monotone Generation -- 4.2 Dualization -- 4.3 Joint Generation BI95,BEGK02,GK95 -- 4.4 Generating (Uniformly) Dual-Bounded Hypergraphs -- 5 More Examples of Generation Problems -- 5.1 Monotone Integer Programming BEGK05,BEGKM01,BEGKM02,BEGKM08 -- 5.2 Maximal Frequent and Minimal Infrequent Sets in Data Mining AMSTV96,BGKM3,Elb06 |
|
5.3 Minimal Strongly Connected Subgraphs and Dicuts BEGKM04 -- 5.4 Generating Generalized Paths, Cuts, and Spanning Sets in Graphs BEGKM07a, BEGKM07,BEGKM08,RT75 -- 5.5 Spanning Linear Spaces by Linear Subspaces BEGK03,BEGKM08a -- 5.6 Polymatroid Functions and Systems of Polymatroid Inequalities BEGK03,BEGKM08a, Lov83,McD75 -- 5.7 Uniformly DB Inequalities for Polymatroid Systems BEGK03,BEGKM08a -- References -- Lower Bounds for Unrestricted Boolean Circuits: Open Problems -- 1 Computational Model: Boolean Circuits -- 2 Lower Bounds: Approaches and Open Problems |
|
2.1 Known Lower Bounds and Gate Elimination Method -- 2.2 Multi-output Functions -- 2.3 Non-gate-Elimination Lower Bounds -- 2.4 Symmetric Functions -- 2.5 Satisfiability Algorithms -- 2.6 Mass Production -- 2.7 Logarithmic Depth Circuits -- 2.8 Linear Circuits and Matrix Rigidity -- 2.9 Multiplicative Complexity -- References -- Online Labeling: Algorithms, Lower Bounds and Open Questions -- 1 The File Maintenance Problem -- 2 Deterministic Algorithms with Arbitrary Universe -- 3 The Role of the Universe Size -- 4 Randomized Online Labeling -- References |
|
Maintaining Chordal Graphs Dynamically: Improved Upper and Lower Bounds -- 1 Introduction -- 1.1 Previous Work -- 1.2 Our Results -- 1.3 Organization of the Paper -- 2 Decremental Algorithms Using Clique Tree -- 2.1 Structure with a Worst Case Update Time -- 2.2 Amortized Analysis -- 3 Dynamic Maintenance of Perfect Elimination Ordering -- 3.1 Decremental Algorithm -- 3.2 Fully Dynamic Maintenance of PEO -- 4 Lower Bound -- 5 Conclusions -- References -- Distributed Symmetry-Breaking Algorithms for Congested Cliques -- 1 Introduction -- 1.1 The Congested Clique Model and Problems |
| Summary |
This book constitutes the proceedings of the 13th International Computer Science Symposium in Russia, CSR 2018, held in Moscow, Russia, in May 2018. The 24 full papers presented together with 7 invited lectures were carefully reviewed and selected from 42 submissions. The papers cover a wide range of topics such as algorithms and data structures; combinatorial optimization; constraint solving; computational complexity; cryptography; combinatorics in computer science; formal languages and automata; algorithms for concurrent and distributed systems; networks; and proof theory and applications of logic to computer science |
| Notes |
International conference proceedings |
| Bibliography |
Includes bibliographical references and author index |
| Notes |
Online resource; title from PDF title page (SpringerLink, viewed May 30, 2018) |
| Subject |
Computer science -- Congresses
|
|
Computer algorithms -- Congresses
|
|
Discrete mathematics.
|
|
Mathematical theory of computation.
|
|
Algorithms & data structures.
|
|
Artificial intelligence.
|
|
Computer programming -- software development.
|
|
Computers -- Data Processing.
|
|
Computers -- Programming -- Algorithms.
|
|
Computers -- Data Modeling & Design.
|
|
Computers -- Intelligence (AI) & Semantics.
|
|
Computers -- Programming -- General.
|
|
Computer algorithms
|
|
Computer science
|
| Genre/Form |
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
| Form |
Electronic book
|
| Author |
Fomin, Fedor V., editor.
|
|
Podolskii, Vladimir V., editor
|
| ISBN |
9783319905303 |
|
3319905309 |
|
3319905295 |
|
9783319905297 |
|
