Buchumschlag

Merge-width and First-Order Model Checking

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Dreier, Jan, Toruńczyk, Szymon
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Combinatorics Discrete Mathematics Data Structures and Algorithms Logic in Computer Science
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Elementary first-order model checking for sparse graphs
von: Gajarský, Jakub, et al.
Veröffentlicht: (2024)

Flipper games for monadically stable graph classes
von: Gajarský, Jakub, et al.
Veröffentlicht: (2023)

Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
von: Dreier, Jan, et al.
Veröffentlicht: (2024)

Flip-width: Cops and Robber on dense graphs
von: Toruńczyk, Szymon
Veröffentlicht: (2023)

Variants of Merge-Width and Applications
von: Drabik, Karolina, et al.
Veröffentlicht: (2026)

CNFs and DNFs with Exactly $k$ Solutions
von: Chandran, L. Sunil, et al.
Veröffentlicht: (2025)

On merge-models
von: Buffière, Hector, et al.
Veröffentlicht: (2026)

Graph classes through the lens of logic
von: Pilipczuk, Michał
Veröffentlicht: (2025)

First-order transducibility among classes of sparse graphs
von: Gajarský, Jakub, et al.
Veröffentlicht: (2025)

Redundancy Is All You Need (for CSP Sparsification)
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2024)

Foundations for an Abstract Proof Theory in the Context of Horn Rules
von: Lyon, Tim S., et al.
Veröffentlicht: (2023)

Solving Partial Dominating Set and Related Problems Using Twin-Width
von: Balabán, Jakub, et al.
Veröffentlicht: (2025)

Formal Primal-Dual Algorithm Analysis
von: Abdulaziz, Mohammad, et al.
Veröffentlicht: (2026)

Color Refinement for Relational Structures
von: Scheidt, Benjamin, et al.
Veröffentlicht: (2024)

The Iteration Number of the Weisfeiler-Leman Algorithm
von: Grohe, Martin, et al.
Veröffentlicht: (2023)

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
von: Grohe, Martin, et al.
Veröffentlicht: (2023)

On classes of bounded tree rank, their interpretations, and efficient sparsification
von: Gajarský, Jakub, et al.
Veröffentlicht: (2024)

Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
von: Koh, Zhuan Khye, et al.
Veröffentlicht: (2021)

SDPs and Robust Satisfiability of Promise CSP
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2022)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
von: Majewski, Konrad, et al.
Veröffentlicht: (2021)

SAT Encoding of Partial Ordering Models for Graph Coloring Problems
von: Faber, Daniel, et al.
Veröffentlicht: (2024)

Separability Properties of Monadically Dependent Graph Classes
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
von: Černý, Marek, et al.
Veröffentlicht: (2025)

Smaller Circuits for Bit Addition
von: Goncharov, Mikhail, et al.
Veröffentlicht: (2025)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
von: Černý, Marek
Veröffentlicht: (2026)

Computing Hamiltonian Paths with Partial Order Restrictions
von: Beisegel, Jesse, et al.
Veröffentlicht: (2024)

The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
von: Dreier, Jan, et al.
Veröffentlicht: (2026)

Twin-width one
von: Ahn, Jungho, et al.
Veröffentlicht: (2025)

A new width parameter of graphs based on edge cuts: $α$-edge-crossing width
von: Chang, Yeonsu, et al.
Veröffentlicht: (2023)

Colouring Probe $H$-Free Graphs
von: Paulusma, Daniël, et al.
Veröffentlicht: (2025)

Moderately beyond clique-width: reduced component max-leaf and related parameters
von: Bonnet, Édouard, et al.
Veröffentlicht: (2026)

Reconfiguration of List Colourings
von: Cambie, Stijn, et al.
Veröffentlicht: (2025)

From Width-Based Model Checking to Width-Based Automated Theorem Proving
von: Oliveira, Mateus de Oliveira, et al.
Veröffentlicht: (2022)

Computing Subset Vertex Covers in $H$-Free Graphs
von: Brettell, Nick, et al.
Veröffentlicht: (2023)

Steiner Forest for $H$-Subgraph-Free Graphs
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2026)

A Unified Model of Congestion Games with Priorities: Two-Sided Markets with Ties, Finite and Non-Affine Delay Functions, and Pure Nash Equilibria
von: Takazawa, Kenjiro
Veröffentlicht: (2024)

The Strong Birthday Problem Revisited
von: Tripathy, Chijul B.
Veröffentlicht: (2025)

Parameterized complexity of isometric path partition: treewidth and diameter
von: Chakraborty, Dibyayan, et al.
Veröffentlicht: (2025)

On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs
von: Ghanbari, Babak, et al.
Veröffentlicht: (2025)

On the Enumeration of all Unique Paths of Recombining Trinomial Trees
von: Torres, Ethan, et al.
Veröffentlicht: (2025)