Copertina

Logarithmic Weisfeiler--Leman and Treewidth

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Levet, Michael, Rombach, Puck, Sieger, Nicholas
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Data Structures and Algorithms Computational Complexity Logic in Computer Science Combinatorics 05C60, 68Q19, 68Q25, 68R10 F.2.2; G.2.2
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
di: Levet, Michael, et al.
Pubblicazione: (2023)

Count-Free Weisfeiler--Leman and Group Isomorphism
di: Collins, Nathaniel A., et al.
Pubblicazione: (2022)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
di: Grochow, Joshua A., et al.
Pubblicazione: (2021)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
di: Grochow, Joshua A., et al.
Pubblicazione: (2025)

Parallel Algorithms for Group Isomorphism via Code Equivalence
di: Levet, Michael
Pubblicazione: (2026)

On the twin-width of near-regular graphs
di: Heinrich, Irene, et al.
Pubblicazione: (2025)

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
di: Golovach, Petr A., et al.
Pubblicazione: (2022)

Treewidth Inapproximability and Tight ETH Lower Bound
di: Bonnet, Édouard
Pubblicazione: (2024)

Optimal non-adaptive algorithm for edge estimation
di: Bishnu, Arijit, et al.
Pubblicazione: (2025)

Answering Related Questions
di: Bonnet, Édouard
Pubblicazione: (2025)

Coloring Hardness on Low Twin-Width Graphs
di: Bonnet, Édouard
Pubblicazione: (2025)

Interval Graphs are Reconstructible
di: Heinrich, Irene, et al.
Pubblicazione: (2025)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
di: Dorochko, Leonid, et al.
Pubblicazione: (2026)

On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures)
di: DasGupta, Bhaskar, et al.
Pubblicazione: (2026)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
di: Philip, Geevarghese, et al.
Pubblicazione: (2026)

Pliability and Approximating Max-CSPs
di: Romero, Miguel, et al.
Pubblicazione: (2019)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
di: Chen, Yijia, et al.
Pubblicazione: (2023)

On Solving Reachability in Grid Digraphs using a Psuedoseparator
di: Jain, Rahul, et al.
Pubblicazione: (2019)

TreeWidzard: An Engine for Width-Based Dynamic Programming and Automated Theorem Proving
di: Oliveria, Mateus de Oliveira, et al.
Pubblicazione: (2026)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
di: Jansen, Klaus, et al.
Pubblicazione: (2024)

On (In)approximability of MaxMin Independent Set Reconfiguration
di: Hoang, Hung P., et al.
Pubblicazione: (2026)

The Word Problem for Products of Symmetric Groups
di: Simon, Hans U.
Pubblicazione: (2025)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
di: Xia, Mingji
Pubblicazione: (2026)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
di: Morse, Gregory, et al.
Pubblicazione: (2026)

Experimental algorithms for the dualization problem
di: Mezzini, Mauro, et al.
Pubblicazione: (2025)

O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold
di: Bell, Tolson, et al.
Pubblicazione: (2024)

A New Temporal Interpretation of Cluster Editing
di: Bocci, Cristiano, et al.
Pubblicazione: (2022)

Mim-Width is paraNP-complete
di: Bergougnoux, Benjamin, et al.
Pubblicazione: (2025)

Overlapping Biclustering
di: Bentert, Matthias, et al.
Pubblicazione: (2025)

Simple minimally unsatisfiable subsets of 2-CNFs
di: Kullmann, Oliver, et al.
Pubblicazione: (2026)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
di: Demaine, Erik D., et al.
Pubblicazione: (2024)

Induced Disjoint Paths Without an Induced Minor
di: Aboulker, Pierre, et al.
Pubblicazione: (2025)

Competitive Query Minimization for Stable Matching with One-Sided Uncertainty
di: Bampis, Evripidis, et al.
Pubblicazione: (2024)

The Gallai Vertex Problem is $Θ_2^p$-Complete
di: Nikabadi, Amir, et al.
Pubblicazione: (2026)

On Solving Simple Curved Nonograms
di: Löffler, Maarten, et al.
Pubblicazione: (2025)

Maximum Matchings in Geometric Intersection Graphs
di: Bonnet, Édouard, et al.
Pubblicazione: (2019)

DAG Scheduling in the BSP Model
di: Papp, Pál András, et al.
Pubblicazione: (2023)

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
di: Bonnet, Édouard, et al.
Pubblicazione: (2026)

A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
di: Hougardy, Stefan, et al.
Pubblicazione: (2025)

On weighted graph separation problems and flow-augmentation
di: Kim, Eun Jung, et al.
Pubblicazione: (2022)