Portal - MFCS 2019

MFCS 2019	August 26-30, 2019, Aachen, Germany
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen (Eds.)
ISBN 978-3-95977-117-7, LIPICS Vol. 138	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 40 MB)
Search Publication Server

Authors

Chakraborty, Sankardeep

Chandrasekaran, Karthekeyan

de Lima, Murilo Santos

Halldórsson, Magnús M.

Kanté, Mamadou Moustapha

Katoen, Joost-Pieter

Kavitha, Telikepalli

Kazeminia, Amirhossein

Khoussainov, Bakhadyr

Konstantinidis, Athanasios L.

Kontinen, Juha

Kortsarz, Guy

Koutsoupias, Elias

Krishna, Shankara Narayanan

Madathil, Jayakrishnan

Rao, B. V. Raghavendra

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Rossmanith, Peter ; Heggernes, Pinar ; Katoen, Joost-Pieter

Abstract | Document (334 KB) | BibTeX

Trustworthy Graph Algorithms (Invited Talk)

Authors: Abdulaziz, Mohammad ; Mehlhorn, Kurt ; Nipkow, Tobias

Abstract | Document (594 KB) | BibTeX

Guarded Kleene Algebra with Tests: Verification of Uninterpreted Programs in Nearly Linear Time (Invited Talk)

Authors: Silva, Alexandra

Abstract | Document (160 KB) | BibTeX

Picking Random Vertices (Invited Talk)

Authors: Lokshtanov, Daniel

Abstract | Document (165 KB) | BibTeX

Popular Matchings: Good, Bad, and Mixed (Invited Talk)

Authors: Kavitha, Telikepalli

Abstract | Document (193 KB) | BibTeX

Petri Net Reachability Problem (Invited Talk)

Authors: Leroux, Jérôme

Abstract | Document (253 KB) | BibTeX

An Improved Online Algorithm for the Traveling Repairperson Problem on a Line

Authors: Bienkowski, Marcin ; Liu, Hsiang-Hsuan

Abstract | Document (408 KB) | BibTeX

Query-Competitive Sorting with Uncertainty

Authors: Halldórsson, Magnús M. ; de Lima, Murilo Santos

Abstract | Document (528 KB) | BibTeX

Better Bounds for Online Line Chasing

Authors: Bienkowski, Marcin ; Byrka, Jaroslaw ; Chrobak, Marek ; Coester, Christian ; Jez, Lukasz ; Koutsoupias, Elias

Abstract | Document (530 KB) | BibTeX

Nash Equilibria in Games over Graphs Equipped with a Communication Mechanism

Authors: Bouyer, Patricia ; Thomasset, Nathan

Abstract | Document (552 KB) | BibTeX

Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time

Authors: Parys, Pawel

Abstract | Document (439 KB) | BibTeX

Bidding Mechanisms in Graph Games

Authors: Avni, Guy ; Henzinger, Thomas A. ; Zikelic, Dorde

Abstract | Document (541 KB) | BibTeX

Cluster Deletion on Interval Graphs and Split Related Graphs

Authors: Konstantinidis, Athanasios L. ; Papadopoulos, Charis

Abstract | Document (700 KB) | BibTeX

Constrained Representations of Map Graphs and Half-Squares

Authors: Le, Hoang-Oanh ; Le, Van Bang

Abstract | Document (532 KB) | BibTeX

Colouring H-Free Graphs of Bounded Diameter

Authors: Martin, Barnaby ; Paulusma, Daniël ; Smith, Siani

Abstract | Document (508 KB) | BibTeX

Distance Labeling Schemes for Cube-Free Median Graphs

Authors: Chepoi, Victor ; Labourel, Arnaud ; Ratel, Sébastien

Abstract | Document (588 KB) | BibTeX

One-Dimensional Guarded Fragments

Authors: Kieronski, Emanuel

Abstract | Document (502 KB) | BibTeX

Finite Satisfiability of Unary Negation Fragment with Transitivity

Authors: Danielski, Daniel ; Kieronski, Emanuel

Abstract | Document (532 KB) | BibTeX

The Fluted Fragment with Transitivity

Authors: Pratt-Hartmann, Ian ; Tendera, Lidia

Abstract | Document (717 KB) | BibTeX

Counting of Teams in First-Order Team Logics

Authors: Haak, Anselm ; Kontinen, Juha ; Müller, Fabian ; Vollmer, Heribert ; Yang, Fan

Abstract | Document (510 KB) | BibTeX

Approximating Activation Edge-Cover and Facility Location Problems

Authors: Nutov, Zeev ; Kortsarz, Guy ; Shalom, Eli

Abstract | Document (627 KB) | BibTeX

Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs

Authors: Konrad, Christian ; Zamaraev, Viktor

Abstract | Document (642 KB) | BibTeX

Multistage Knapsack

Authors: Bampis, Evripidis ; Escoffier, Bruno ; Teiller, Alexandre

Abstract | Document (544 KB) | BibTeX

Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations

Authors: Bournez, Olivier ; Durand, Arnaud

Abstract | Document (507 KB) | BibTeX

On the Coalgebra of Partial Differential Equations

Authors: Boreale, Michele

Abstract | Document (492 KB) | BibTeX

Random Subgroups of Rationals

Authors: Gao, Ziyuan ; Jain, Sanjay ; Khoussainov, Bakhadyr ; Li, Wei ; Melnikov, Alexander ; Seidel, Karen ; Stephan, Frank

Abstract | Document (493 KB) | BibTeX

Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness

Authors: Dörfler, Julian ; Roth, Marc ; Schmitt, Johannes ; Wellnitz, Philip

Abstract | Document (494 KB) | BibTeX

Packing Arc-Disjoint Cycles in Tournaments

Authors: Bessy, Stéphane ; Bougeret, Marin ; Krithika, R. ; Sahu, Abhishek ; Saurabh, Saket ; Thiebaut, Jocelyn ; Zehavi, Meirav

Abstract | Document (567 KB) | BibTeX

A Sub-Exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs

Authors: Madathil, Jayakrishnan ; Sharma, Roohani ; Zehavi, Meirav

Abstract | Document (604 KB) | BibTeX

The Quantifier Alternation Hierarchy of Synchronous Relations

Authors: Figueira, Diego ; Ramanathan, Varun ; Weil, Pascal

Abstract | Document (739 KB) | BibTeX

Two variable fragment of Term Modal Logic

Authors: Padmanabha, Anantha ; Ramanujam, R.

Abstract | Document (1,485 KB) | BibTeX

Choiceless Logarithmic Space

Authors: Grädel, Erich ; Schalthöfer, Svenja

Abstract | Document (524 KB) | BibTeX

Faster FPT Algorithm for 5-Path Vertex Cover

Authors: Cervený, Radovan ; Suchý, Ondrej

Abstract | Document (479 KB) | BibTeX

Parameterized Complexity of Fair Vertex Evaluation Problems

Authors: Knop, Dusan ; Masarík, Tomás ; Toufar, Tomás

Abstract | Document (575 KB) | BibTeX

A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs

Authors: Jaffke, Lars ; Lima, Paloma T.

Abstract | Document (652 KB) | BibTeX

Parameterized Complexity of Conflict-Free Matchings and Paths

Authors: Agrawal, Akanksha ; Jain, Pallavi ; Kanesh, Lawqueen ; Saurabh, Saket

Abstract | Document (643 KB) | BibTeX

On the Strength of Uniqueness Quantification in Primitive Positive Formulas

Authors: Lagerkvist, Victor ; Nordh, Gustav

Abstract | Document (564 KB) | BibTeX

Resolution Lower Bounds for Refutation Statements

Authors: Garlík, Michal

Abstract | Document (461 KB) | BibTeX

Tangles and Single Linkage Hierarchical Clustering

Authors: Fluck, Eva

Abstract | Document (457 KB) | BibTeX

Approximating the Orthogonality Dimension of Graphs and Hypergraphs

Authors: Haviv, Ishay

Abstract | Document (499 KB) | BibTeX

Domination Above r-Independence: Does Sparseness Help?

Authors: Einarson, Carl ; Reidl, Felix

Abstract | Document (584 KB) | BibTeX

Reducing the Domination Number of Graphs via Edge Contractions

Authors: Galby, Esther ; Lima, Paloma T. ; Ries, Bernard

Abstract | Document (509 KB) | BibTeX

Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth

Authors: Eiben, Eduard ; Ganian, Robert ; Hamm, Thekla ; Kwon, O-joung

Abstract | Document (597 KB) | BibTeX

The Power Word Problem

Authors: Lohrey, Markus ; Weiß, Armin

Abstract | Document (539 KB) | BibTeX

Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations

Authors: Day, Joel D. ; Manea, Florin ; Nowotka, Dirk

Abstract | Document (516 KB) | BibTeX

The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs

Authors: Kiefer, Sandra ; Neuen, Daniel

Abstract | Document (495 KB) | BibTeX

The Domino Problem is Undecidable on Surface Groups

Authors: Aubrun, Nathalie ; Barbieri, Sebastián ; Moutot, Etienne

Abstract | Document (604 KB) | BibTeX

P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle

Authors: Dose, Titus

Abstract | Document (492 KB) | BibTeX

Semicomputable Points in Euclidean Spaces

Authors: Hoyrup, Mathieu ; Stull, Donald M.

Abstract | Document (469 KB) | BibTeX

Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs

Authors: Galesi, Nicola ; Itsykson, Dmitry ; Riazanov, Artur ; Sofronova, Anastasia

Abstract | Document (550 KB) | BibTeX

On the Expressivity of Linear Recursion Schemes

Authors: Clairambault, Pierre ; Murawski, Andrzej S.

Abstract | Document (694 KB) | BibTeX

Uniform Random Expressions Lack Expressivity

Authors: Koechlin, Florent ; Nicaud, Cyril ; Rotondo, Pablo

Abstract | Document (570 KB) | BibTeX

Lower Bounds for Multilinear Order-Restricted ABPs

Authors: Ramya, C. ; Rao, B. V. Raghavendra

Abstract | Document (583 KB) | BibTeX

On the Symmetries of and Equivalence Test for Design Polynomials

Authors: Gupta, Nikhil ; Saha, Chandan

Abstract | Document (599 KB) | BibTeX

The Complexity of Homomorphism Indistinguishability

Authors: Böker, Jan ; Chen, Yijia ; Grohe, Martin ; Rattan, Gaurav

Abstract | Document (528 KB) | BibTeX

SZX-Calculus: Scalable Graphical Quantum Reasoning

Authors: Carette, Titouan ; Horsman, Dominic ; Perdrix, Simon

Abstract | Document (670 KB) | BibTeX

On the Stretch Factor of Polygonal Chains

Authors: Chen, Ke ; Dumitrescu, Adrian ; Mulzer, Wolfgang ; Tóth, Csaba D.

Abstract | Document (505 KB) | BibTeX

Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks

Authors: Enright, Jessica ; Meeks, Kitty ; Mertzios, George B. ; Zamaraev, Viktor

Abstract | Document (523 KB) | BibTeX

Constant Delay Enumeration with FPT-Preprocessing for Conjunctive Queries of Bounded Submodular Width

Authors: Berkholz, Christoph ; Schweikardt, Nicole

Abstract | Document (588 KB) | BibTeX

Counting Homomorphisms Modulo a Prime Number

Authors: Kazeminia, Amirhossein ; Bulatov, Andrei A.

Abstract | Document (585 KB) | BibTeX

Approximate Counting CSP Seen from the Other Side

Authors: Bulatov, Andrei A. ; Zivný, Stanislav

Abstract | Document (535 KB) | BibTeX

Uniformisation Gives the Full Strength of Regular Languages

Authors: Lhote, Nathan ; Michielini, Vincent ; Skrzypczak, Michal

Abstract | Document (515 KB) | BibTeX

New Pumping Technique for 2-Dimensional VASS

Authors: Czerwinski, Wojciech ; Lasota, Slawomir ; Löding, Christof ; Piórkowski, Radoslaw

Abstract | Document (509 KB) | BibTeX

Computational Complexity of Synchronization under Regular Constraints

Authors: Fernau, Henning ; Gusev, Vladimir V. ; Hoffmann, Stefan ; Holzer, Markus ; Volkov, Mikhail V. ; Wolf, Petra

Abstract | Document (569 KB) | BibTeX

A Constant-Time Colored Choice Dictionary with Almost Robust Iteration

Authors: Hagerup, Torben

Abstract | Document (497 KB) | BibTeX

Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient

Authors: Baswana, Surender ; Gupta, Shiv ; Tulsyan, Ayush

Abstract | Document (558 KB) | BibTeX

RLE Edit Distance in Near Optimal Time

Authors: Clifford, Raphaël ; Gawrychowski, Pawel ; Kociumaka, Tomasz ; Martin, Daniel P. ; Uznanski, Przemyslaw

Abstract | Document (555 KB) | BibTeX

Indexing Graph Search Trees and Applications

Authors: Chakraborty, Sankardeep ; Sadakane, Kunihiko

Abstract | Document (451 KB) | BibTeX

Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties

Authors: Dennunzio, Alberto ; Formenti, Enrico ; Grinberg, Darij ; Margara, Luciano

Abstract | Document (509 KB) | BibTeX

On Synthesis of Resynchronizers for Transducers

Authors: Bose, Sougata ; Krishna, Shankara Narayanan ; Muscholl, Anca ; Penelle, Vincent ; Puppis, Gabriele

Abstract | Document (600 KB) | BibTeX

Acceptance Ambiguity for Quantum Automata

Authors: Bell, Paul C. ; Hirvensalo, Mika

Abstract | Document (488 KB) | BibTeX

From Regular Expression Matching to Parsing

Authors: Bille, Philip ; Gørtz, Inge Li

Abstract | Document (1,220 KB) | BibTeX

Solving Systems of Equations in Supernilpotent Algebras

Authors: Aichinger, Erhard

Abstract | Document (560 KB) | BibTeX

Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs

Authors: Conte, Alessio ; Grossi, Roberto ; Kanté, Mamadou Moustapha ; Marino, Andrea ; Uno, Takeaki ; Wasa, Kunihiro

Abstract | Document (604 KB) | BibTeX

Enumeration of Preferred Extensions in Almost Oriented Digraphs

Authors: Gaspers, Serge ; Li, Ray

Abstract | Document (547 KB) | BibTeX

Determinisation of Finitely-Ambiguous Copyless Cost Register Automata

Authors: Lopez, Théodore ; Monmege, Benjamin ; Talbot, Jean-Marc

Abstract | Document (503 KB) | BibTeX

Aperiodic Weighted Automata and Weighted First-Order Logic

Authors: Droste, Manfred ; Gastin, Paul

Abstract | Document (498 KB) | BibTeX

A Congruence-based Perspective on Automata Minimization Algorithms

Authors: Ganty, Pierre ; Gutiérrez, Elena ; Valero, Pedro

Abstract | Document (540 KB) | BibTeX

Finding Optimal Solutions With Neighborly Help

Authors: Burjons, Elisabet ; Frei, Fabian ; Hemaspaandra, Edith ; Komm, Dennis ; Wehner, David

Abstract | Document (446 KB) | BibTeX

Reconfiguration of Minimum Steiner Trees via Vertex Exchanges

Authors: Mizuta, Haruka ; Hatanaka, Tatsuhiko ; Ito, Takehiro ; Zhou, Xiao

Abstract | Document (511 KB) | BibTeX

The Perfect Matching Reconfiguration Problem

Authors: Bonamy, Marthe ; Bousquet, Nicolas ; Heinrich, Marc ; Ito, Takehiro ; Kobayashi, Yusuke ; Mary, Arnaud ; Mühlenthaler, Moritz ; Wasa, Kunihiro

Abstract | Document (1,086 KB) | BibTeX

Spectral Aspects of Symmetric Matrix Signings

Authors: Carlson, Charles ; Chandrasekaran, Karthekeyan ; Chang, Hsien-Chih ; Kakimura, Naonori ; Kolla, Alexandra

Abstract | Document (546 KB) | BibTeX

Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques

Authors: Kiefer, Stefan ; Widdershoven, Cas

Abstract | Document (481 KB) | BibTeX

On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond

Authors: Bell, Paul C. ; Potapov, Igor ; Semukhin, Pavel

Abstract | Document (544 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)