Representation of Short Distances in Structurally Sparse Graphs (English)
Free access
- New search for: Dvořák, Zdeněk
- Further information on Dvořák, Zdeněk:
- https://orcid.org/0000-0002-8308-9746
- New search for: Dvořák, Zdeněk
- Further information on Dvořák, Zdeněk:
- https://orcid.org/0000-0002-8308-9746
- New search for: Berenbrink, Petra
- New search for: Bouyer, Patricia
- Further information on Bouyer, Patricia:
- https://orcid.org/0000-0002-2823-0911
- New search for: Dawar, Anuj
- Further information on Dawar, Anuj:
- https://orcid.org/0000-0003-4014-8248
- New search for: Kanté, Mamadou Moustapha
- Further information on Kanté, Mamadou Moustapha:
- https://orcid.org/0000-0003-1838-7744
In:
LIPIcs, Volume 254, STACS 2023
: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
;
254
;
28:1-28:22
;
2023
-
ISBN:
-
ISSN:
- Conference paper / Electronic Resource
-
Title:Representation of Short Distances in Structurally Sparse Graphs
-
Contributors:Dvořák, Zdeněk ( author ) / Berenbrink, Petra ( editor ) / Bouyer, Patricia ( editor ) / Dawar, Anuj ( editor ) / Kanté, Mamadou Moustapha ( editor )
-
Published in:LIPIcs, Volume 254, STACS 2023 : 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) ; 254 ; 28:1-28:22Leibniz International Proceedings in Informatics (LIPIcs) ; 254 ; 28:1-28:22
-
Publisher:
- New search for: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Publication date:2023-03-03
-
Size:22 pages , 781368 byte
-
Remarks:LIPIcs, Vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 28:1-28:22
-
ISBN:
-
ISSN:
-
DOI:
-
Type of media:Conference paper
-
Type of material:Electronic Resource
-
Language:English
-
Keywords:
-
Licence:
-
Source:
Table of contents conference proceedings
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
A Brief History of History-Determinism (Invited Talk)Lehtinen, Karoliina et al. | 2023
- 2
-
Amortised Analysis of Dynamic Data Structures (Invited Talk)Rotenberg, Eva et al. | 2023
- 3
-
Logical Algorithmics: From Theory to Practice (Invited Talk)Vardi, Moshe Y. et al. | 2023
- 4
-
The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev TermAichinger, Erhard / Grünbacher, Simon et al. | 2023
- 5
-
Packing Odd Walks and Trails in Multiterminal NetworksAkhmedov, Maxim / Babenko, Maxim et al. | 2023
- 6
-
Improved Weighted Matching in the Sliding Window ModelAlexandru, Cezar-Mihail / Dvořák, Pavel / Konrad, Christian / Naidu, Kheeran K. et al. | 2023
- 7
-
Approximate Sampling and Counting of Graphs with Near-Regular Degree IntervalsAmanatidis, Georgios / Kleer, Pieter et al. | 2023
- 8
-
Enumerating Regular Languages with Bounded DelayAmarilli, Antoine / Monet, Mikaël et al. | 2023
- 9
-
Regular Separability in Büchi VASSBaumann, Pascal / Meyer, Roland / Zetzsche, Georg et al. | 2023
- 10
-
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-WidthBergé, Pierre / Bonnet, Édouard / Déprés, Hugues / Watrigant, Rémi et al. | 2023
- 11
-
Tight Lower Bounds for Problems Parameterized by Rank-WidthBergougnoux, Benjamin / Korhonen, Tuukka / Nederlof, Jesper et al. | 2023
- 12
-
On the Multilinear Complexity of Associative AlgebrasBläser, Markus / Mayer, Hendrik / Shringi, Devansh et al. | 2023
- 13
-
Strongly Hyperbolic Unit Disk GraphsBläsius, Thomas / Friedrich, Tobias / Katzmann, Maximilian / Stephan, Daniel et al. | 2023
- 14
-
Tight Bounds for Connectivity Problems Parameterized by CutwidthBojikian, Narek / Chekan, Vera / Hegerfeld, Falko / Kratsch, Stefan et al. | 2023
- 15
-
Twin-Width V: Linear Minors, Modular Counting, and Matrix MultiplicationBonnet, Édouard / Giocanti, Ugo / Ossona de Mendez, Patrice / Thomassé, Stéphan et al. | 2023
- 16
-
Non-Adaptive Proper Learning PolynomialsBshouty, Nader H. et al. | 2023
- 17
-
Cut Paths and Their Remainder Structure, with ApplicationsCairo, Massimo / Khan, Shahbaz / Rizzi, Romeo / Schmidt, Sebastian / Tomescu, Alexandru I. / Zirondelli, Elia C. et al. | 2023
- 18
-
Geometric Amortization of Enumeration AlgorithmsCapelli, Florent / Strozecki, Yann et al. | 2023
- 19
-
One Drop of Non-Determinism in a Random Deterministic AutomatonCarayol, Arnaud / Duchon, Philippe / Koechlin, Florent / Nicaud, Cyril et al. | 2023
- 20
-
Improved NP-Hardness of Approximation for Orthogonality Dimension and MinrankChawin, Dror / Haviv, Ishay et al. | 2023
- 21
-
Extending Merge Resolution to a Family of QBF-Proof SystemsChede, Sravanthi / Shukla, Anil et al. | 2023
- 22
-
On Hardness of Testing Equivalence to Sparse Polynomials Under ShiftsChillara, Suryajith / Grichener, Coral / Shpilka, Amir et al. | 2023
- 23
-
Online Paging with Heterogeneous Cache SlotsChrobak, Marek / Haney, Samuel / Liaee, Mehraneh / Panigrahi, Debmalya / Rajaraman, Rajmohan / Sundaram, Ravi / Young, Neal E. et al. | 2023
- 24
-
On Rational Recursive SequencesClemente, Lorenzo / Donten-Bury, Maria / Mazowiecki, Filip / Pilipczuk, Michał et al. | 2023
- 25
-
Semigroup Intersection Problems in the Heisenberg GroupsDong, Ruiwen et al. | 2023
- 26
-
Solving Homogeneous Linear Equations over Polynomial SemiringsDong, Ruiwen et al. | 2023
- 27
-
An Approximation Algorithm for Distance-Constrained Vehicle Routing on TreesDufay, Marc / Mathieu, Claire / Zhou, Hang et al. | 2023
- 28
-
Representation of Short Distances in Structurally Sparse GraphsDvořák, Zdeněk et al. | 2023
- 29
-
Exact Matching: Algorithms and Related ProblemsEl Maalouly, Nicolas et al. | 2023
- 30
-
Counting Temporal PathsEnright, Jessica / Meeks, Kitty / Molter, Hendrik et al. | 2023
- 31
-
Barriers for Faster Dimensionality ReductionNova Fandina, Ora / Møller Høgsgaard, Mikael / Green Larsen, Kasper et al. | 2023
- 32
-
A Regular and Complete Notion of Delay for Streaming String TransducersFiliot, Emmanuel / Jecker, Ismaël / Löding, Christof / Winter, Sarah et al. | 2023
- 33
-
New Clocks, Optimal Line Formation and Self-Replication Population ProtocolsGąsieniec, Leszek / Spirakis, Paul G. / Stachowiak, Grzegorz et al. | 2023
- 34
-
Avoidance Games Are PSPACE-CompleteGledel, Valentin / Oijid, Nacim et al. | 2023
- 35
-
Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-CompositionsHeeger, Klaus / Nichterlein, André / Niedermeier, Rolf et al. | 2023
- 36
-
Dynamic Maintenance of Monotone Dynamic Programs and ApplicationsHenzinger, Monika / Neumann, Stefan / Räcke, Harald / Schmid, Stefan et al. | 2023
- 37
-
Approximate Selection with Unreliable Comparisons in Optimal Expected TimeHuang, Shengyu / Liu, Chih-Hung / Rutschmann, Daniel et al. | 2023
- 38
-
Relating Description Complexity to EntropyJaakkola, Reijo / Kuusisto, Antti / Vilander, Miikka et al. | 2023
- 39
-
Induced Matching Below Guarantees: Average Paves the Way for Fixed-Parameter TractabilityKoana, Tomohiro et al. | 2023
- 40
-
Finding and Counting Patterns in Sparse GraphsKomarath, Balagopal / Kumar, Anant / Mishra, Suchismita / Sethia, Aditi et al. | 2023
- 41
-
Maximum Matching via Maximal Matching QueriesKonrad, Christian / Naidu, Kheeran K. / Steward, Arun et al. | 2023
- 42
-
Distributed Quantum Interactive ProofsLe Gall, François / Miyamoto, Masayuki / Nishimura, Harumichi et al. | 2023
- 43
-
Reconfiguration of Digraph HomomorphismsLévêque, Benjamin / Mühlenthaler, Moritz / Suzan, Thomas et al. | 2023
- 44
-
An 𝒪(3.82^k) Time FPT Algorithm for Convex Flip DistanceLi, Haohong / Xia, Ge et al. | 2023
- 45
-
Tight Bounds for Repeated Balls-Into-BinsLos, Dimitrios / Sauerwald, Thomas et al. | 2023
- 46
-
Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex NumberMajewski, Konrad / Pilipczuk, Michał / Sokołowski, Marek et al. | 2023
- 47
-
Sublinear-Time Probabilistic Cellular AutomataModanese, Augusto et al. | 2023
- 48
-
Real Numbers Equally Compressible in Every BaseNandakumar, Satyadev / Pulari, Subin et al. | 2023
- 49
-
Gap Preserving Reductions Between Reconfiguration ProblemsOhsaka, Naoto et al. | 2023
- 50
-
Dynamic Data Structures for Parameterized String ProblemsOlkowski, Jędrzej / Pilipczuk, Michał / Rychlicki, Mateusz / Węgrzycki, Karol / Zych-Pawlewicz, Anna et al. | 2023
- 51
-
An Algebraic Approach to Vectorial ProgramsPaperman, Charles / Salvati, Sylvain / Soyez-Martin, Claire et al. | 2023
- 52
-
Reconstructing Words Using Queries on Subwords or FactorsRichomme, Gwenaël / Rosenfeld, Matthieu et al. | 2023
- 53
-
Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future AlgorithmSadeh, Yaniv / Kaplan, Haim et al. | 2023
- 54
-
The Complexity of Translationally Invariant Problems Beyond Ground State EnergiesWatson, James D. / Bausch, Johannes / Gharibian, Sevag et al. | 2023
- 55
-
Restless Temporal Path Parameterized Above Lower BoundsZschoche, Philipp et al. | 2023