![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
44th MFCS 2019: Aachen, Germany
- Peter Rossmanith
, Pinar Heggernes
, Joost-Pieter Katoen
:
44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany. LIPIcs 138, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2019, ISBN 978-3-95977-117-7 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:16
- Mohammad Abdulaziz
, Kurt Mehlhorn, Tobias Nipkow:
Trustworthy Graph Algorithms (Invited Talk). 1:1-1:22 - Alexandra Silva:
Guarded Kleene Algebra with Tests: Verification of Uninterpreted Programs in Nearly Linear Time (Invited Talk). 2:1-2:1 - Daniel Lokshtanov:
Picking Random Vertices (Invited Talk). 3:1-3:1 - Telikepalli Kavitha:
Popular Matchings: Good, Bad, and Mixed (Invited Talk). 4:1-4:1 - Jérôme Leroux:
Petri Net Reachability Problem (Invited Talk). 5:1-5:3 - Marcin Bienkowski
, Hsiang-Hsuan Liu
:
An Improved Online Algorithm for the Traveling Repairperson Problem on a Line. 6:1-6:12 - Magnús M. Halldórsson
, Murilo Santos de Lima
:
Query-Competitive Sorting with Uncertainty. 7:1-7:15 - Marcin Bienkowski
, Jaroslaw Byrka
, Marek Chrobak
, Christian Coester
, Lukasz Jez
, Elias Koutsoupias
:
Better Bounds for Online Line Chasing. 8:1-8:13 - Patricia Bouyer
, Nathan Thomasset:
Nash Equilibria in Games over Graphs Equipped with a Communication Mechanism. 9:1-9:14 - Pawel Parys
:
Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time. 10:1-10:13 - Guy Avni
, Thomas A. Henzinger, Dorde Zikelic:
Bidding Mechanisms in Graph Games. 11:1-11:13 - Athanasios L. Konstantinidis, Charis Papadopoulos
:
Cluster Deletion on Interval Graphs and Split Related Graphs. 12:1-12:14 - Hoàng-Oanh Le, Van Bang Le:
Constrained Representations of Map Graphs and Half-Squares. 13:1-13:15 - Barnaby Martin
, Daniël Paulusma
, Siani Smith
:
Colouring H-Free Graphs of Bounded Diameter. 14:1-14:14 - Victor Chepoi, Arnaud Labourel, Sébastien Ratel:
Distance Labeling Schemes for Cube-Free Median Graphs. 15:1-15:14 - Emanuel Kieronski
:
One-Dimensional Guarded Fragments. 16:1-16:14 - Daniel Danielski
, Emanuel Kieronski
:
Finite Satisfiability of Unary Negation Fragment with Transitivity. 17:1-17:15 - Ian Pratt-Hartmann
, Lidia Tendera
:
The Fluted Fragment with Transitivity. 18:1-18:15 - Anselm Haak
, Juha Kontinen
, Fabian Müller, Heribert Vollmer
, Fan Yang
:
Counting of Teams in First-Order Team Logics. 19:1-19:15 - Zeev Nutov, Guy Kortsarz, Eli Shalom:
Approximating Activation Edge-Cover and Facility Location Problems. 20:1-20:14 - Christian Konrad, Viktor Zamaraev
:
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs. 21:1-21:15 - Evripidis Bampis
, Bruno Escoffier, Alexandre Teiller:
Multistage Knapsack. 22:1-22:14 - Olivier Bournez
, Arnaud Durand:
Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations. 23:1-23:14 - Michele Boreale
:
On the Coalgebra of Partial Differential Equations. 24:1-24:13 - Ziyuan Gao, Sanjay Jain
, Bakhadyr Khoussainov, Wei Li, Alexander G. Melnikov
, Karen Seidel, Frank Stephan
:
Random Subgroups of Rationals. 25:1-25:14 - Julian Dörfler
, Marc Roth
, Johannes Schmitt
, Philip Wellnitz
:
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness. 26:1-26:14 - Stéphane Bessy, Marin Bougeret
, R. Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut
, Meirav Zehavi:
Packing Arc-Disjoint Cycles in Tournaments. 27:1-27:14 - Jayakrishnan Madathil
, Roohani Sharma, Meirav Zehavi:
A Sub-Exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs. 28:1-28:14 - Diego Figueira
, Varun Ramanathan, Pascal Weil:
The Quantifier Alternation Hierarchy of Synchronous Relations. 29:1-29:14 - Anantha Padmanabha
, R. Ramanujam:
Two variable fragment of Term Modal Logic. 30:1-30:14 - Erich Grädel, Svenja Schalthöfer
:
Choiceless Logarithmic Space. 31:1-31:15 - Radovan Cervený
, Ondrej Suchý
:
Faster FPT Algorithm for 5-Path Vertex Cover. 32:1-32:13 - Dusan Knop
, Tomás Masarík
, Tomás Toufar:
Parameterized Complexity of Fair Vertex Evaluation Problems. 33:1-33:16 - Lars Jaffke
, Paloma T. Lima:
A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs. 34:1-34:13 - Akanksha Agrawal
, Pallavi Jain, Lawqueen Kanesh, Saket Saurabh:
Parameterized Complexity of Conflict-Free Matchings and Paths. 35:1-35:15 - Victor Lagerkvist, Gustav Nordh:
On the Strength of Uniqueness Quantification in Primitive Positive Formulas. 36:1-36:15 - Michal Garlík:
Resolution Lower Bounds for Refutation Statements. 37:1-37:13 - Eva Fluck
:
Tangles and Single Linkage Hierarchical Clustering. 38:1-38:12 - Ishay Haviv:
Approximating the Orthogonality Dimension of Graphs and Hypergraphs. 39:1-39:15 - Carl Einarson, Felix Reidl
:
Domination Above r-Independence: Does Sparseness Help? 40:1-40:13 - Esther Galby
, Paloma T. Lima, Bernard Ries
:
Reducing the Domination Number of Graphs via Edge Contractions. 41:1-41:13 - Eduard Eiben
, Robert Ganian, Thekla Hamm
, O-joung Kwon:
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. 42:1-42:15 - Markus Lohrey, Armin Weiß
:
The Power Word Problem. 43:1-43:15 - Joel D. Day, Florin Manea, Dirk Nowotka:
Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations. 44:1-44:15 - Sandra Kiefer
, Daniel Neuen
:
The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs. 45:1-45:15 - Nathalie Aubrun, Sebastián Barbieri
, Etienne Moutot
:
The Domino Problem is Undecidable on Surface Groups. 46:1-46:14 - Titus Dose:
P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle. 47:1-47:14 - Mathieu Hoyrup, Donald M. Stull:
Semicomputable Points in Euclidean Spaces. 48:1-48:13 - Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova:
Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs. 49:1-49:15 - Pierre Clairambault, Andrzej S. Murawski:
On the Expressivity of Linear Recursion Schemes. 50:1-50:14 - Florent Koechlin, Cyril Nicaud, Pablo Rotondo:
Uniform Random Expressions Lack Expressivity. 51:1-51:14 - C. Ramya, B. V. Raghavendra Rao:
Lower Bounds for Multilinear Order-Restricted ABPs. 52:1-52:14 - Nikhil Gupta, Chandan Saha:
On the Symmetries of and Equivalence Test for Design Polynomials. 53:1-53:16 - Jan Böker
, Yijia Chen
, Martin Grohe
, Gaurav Rattan
:
The Complexity of Homomorphism Indistinguishability. 54:1-54:13 - Titouan Carette
, Dominic Horsman, Simon Perdrix
:
SZX-Calculus: Scalable Graphical Quantum Reasoning. 55:1-55:15 - Ke Chen
, Adrian Dumitrescu
, Wolfgang Mulzer
, Csaba D. Tóth:
On the Stretch Factor of Polygonal Chains. 56:1-56:14 - Jessica A. Enright
, Kitty Meeks, George B. Mertzios, Viktor Zamaraev
:
Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks. 57:1-57:15 - Christoph Berkholz, Nicole Schweikardt:
Constant Delay Enumeration with FPT-Preprocessing for Conjunctive Queries of Bounded Submodular Width. 58:1-58:15 - Amirhossein Kazeminia, Andrei A. Bulatov:
Counting Homomorphisms Modulo a Prime Number. 59:1-59:13 - Andrei A. Bulatov, Stanislav Zivný
:
Approximate Counting CSP Seen from the Other Side. 60:1-60:14 - Nathan Lhote, Vincent Michielini, Michal Skrzypczak:
Uniformisation Gives the Full Strength of Regular Languages. 61:1-61:13 - Wojciech Czerwinski
, Slawomir Lasota
, Christof Löding, Radoslaw Piórkowski
:
New Pumping Technique for 2-Dimensional VASS. 62:1-62:14 - Henning Fernau
, Vladimir V. Gusev
, Stefan Hoffmann
, Markus Holzer
, Mikhail V. Volkov
, Petra Wolf
:
Computational Complexity of Synchronization under Regular Constraints. 63:1-63:14 - Torben Hagerup
:
A Constant-Time Colored Choice Dictionary with Almost Robust Iteration. 64:1-64:14 - Surender Baswana, Shiv Kumar Gupta, Ayush Tulsyan:
Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient. 65:1-65:16 - Raphaël Clifford
, Pawel Gawrychowski
, Tomasz Kociumaka
, Daniel P. Martin
, Przemyslaw Uznanski
:
RLE Edit Distance in Near Optimal Time. 66:1-66:13 - Sankardeep Chakraborty, Kunihiko Sadakane:
Indexing Graph Search Trees and Applications. 67:1-67:14 - Alberto Dennunzio, Enrico Formenti
, Darij Grinberg, Luciano Margara
:
Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties. 68:1-68:15 - Sougata Bose
, Shankara Narayanan Krishna, Anca Muscholl, Vincent Penelle, Gabriele Puppis
:
On Synthesis of Resynchronizers for Transducers. 69:1-69:14 - Paul C. Bell
, Mika Hirvensalo:
Acceptance Ambiguity for Quantum Automata. 70:1-70:14 - Philip Bille
, Inge Li Gørtz
:
From Regular Expression Matching to Parsing. 71:1-71:14 - Erhard Aichinger
:
Solving Systems of Equations in Supernilpotent Algebras. 72:1-72:9 - Alessio Conte, Roberto Grossi, Mamadou Moustapha Kanté, Andrea Marino, Takeaki Uno, Kunihiro Wasa:
Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs. 73:1-73:14 - Serge Gaspers, Ray Li:
Enumeration of Preferred Extensions in Almost Oriented Digraphs. 74:1-74:15 - Théodore Lopez, Benjamin Monmege
, Jean-Marc Talbot:
Determinisation of Finitely-Ambiguous Copyless Cost Register Automata. 75:1-75:15 - Manfred Droste, Paul Gastin
:
Aperiodic Weighted Automata and Weighted First-Order Logic. 76:1-76:15 - Pierre Ganty
, Elena Gutiérrez, Pedro Valero
:
A Congruence-based Perspective on Automata Minimization Algorithms. 77:1-77:14 - Elisabet Burjons
, Fabian Frei, Edith Hemaspaandra, Dennis Komm
, David Wehner:
Finding Optimal Solutions With Neighborly Help. 78:1-78:14 - Haruka Mizuta, Tatsuhiko Hatanaka, Takehiro Ito
, Xiao Zhou:
Reconfiguration of Minimum Steiner Trees via Vertex Exchanges. 79:1-79:11 - Marthe Bonamy, Nicolas Bousquet
, Marc Heinrich, Takehiro Ito
, Yusuke Kobayashi, Arnaud Mary
, Moritz Mühlenthaler, Kunihiro Wasa
:
The Perfect Matching Reconfiguration Problem. 80:1-80:14 - Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Naonori Kakimura, Alexandra Kolla:
Spectral Aspects of Symmetric Matrix Signings. 81:1-81:13 - Stefan Kiefer, Cas Widdershoven:
Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques. 82:1-82:13 - Paul C. Bell
, Igor Potapov
, Pavel Semukhin
:
On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond. 83:1-83:15
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.