Imagen de Portada

SAT Encoding of Partial Ordering Models for Graph Coloring Problems

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Faber, Daniel, Jabrayilov, Adalat, Mutzel, Petra
Formato:	Preprint
Publicado:	2024
Materias:	Artificial Intelligence Discrete Mathematics Data Structures and Algorithms Logic in Computer Science
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A Customized SAT-based Solver for Graph Coloring
por: Brand, Timo, et al.
Publicado: (2025)

Solving Partial Dominating Set and Related Problems Using Twin-Width
por: Balabán, Jakub, et al.
Publicado: (2025)

Color Refinement for Relational Structures
por: Scheidt, Benjamin, et al.
Publicado: (2024)

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
por: Grohe, Martin, et al.
Publicado: (2023)

The Iteration Number of the Weisfeiler-Leman Algorithm
por: Grohe, Martin, et al.
Publicado: (2023)

Foundations for an Abstract Proof Theory in the Context of Horn Rules
por: Lyon, Tim S., et al.
Publicado: (2023)

Graph classes through the lens of logic
por: Pilipczuk, Michał
Publicado: (2025)

On classes of bounded tree rank, their interpretations, and efficient sparsification
por: Gajarský, Jakub, et al.
Publicado: (2024)

Formal Primal-Dual Algorithm Analysis
por: Abdulaziz, Mohammad, et al.
Publicado: (2026)

Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
por: Koh, Zhuan Khye, et al.
Publicado: (2021)

SDPs and Robust Satisfiability of Promise CSP
por: Brakensiek, Joshua, et al.
Publicado: (2022)

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

Elementary first-order model checking for sparse graphs
por: Gajarský, Jakub, et al.
Publicado: (2024)

On merge-models
por: Buffière, Hector, et al.
Publicado: (2026)

CNFs and DNFs with Exactly $k$ Solutions
por: Chandran, L. Sunil, et al.
Publicado: (2025)

Flipper games for monadically stable graph classes
por: Gajarský, Jakub, et al.
Publicado: (2023)

Merge-width and First-Order Model Checking
por: Dreier, Jan, et al.
Publicado: (2025)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
por: Černý, Marek
Publicado: (2026)

Partially Ordered Sets Corresponding to the Partition Problem
por: Kubo, Susumu
Publicado: (2024)

From Width-Based Model Checking to Width-Based Automated Theorem Proving
por: Oliveira, Mateus de Oliveira, et al.
Publicado: (2022)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
por: Černý, Marek, et al.
Publicado: (2025)

Smaller Circuits for Bit Addition
por: Goncharov, Mikhail, et al.
Publicado: (2025)

Asymptotically Smaller Encodings for Graph Problems and Scheduling
por: Subercaseaux, Bernardo
Publicado: (2025)

SAT Requires Exhaustive Search
por: Xu, Ke, et al.
Publicado: (2023)

A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates
por: Weiss, Eyal, et al.
Publicado: (2022)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths
por: Beisegel, Jesse, et al.
Publicado: (2025)

Redundancy Is All You Need (for CSP Sparsification)
por: Brakensiek, Joshua, et al.
Publicado: (2024)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
por: Dudeja, Aditi, et al.
Publicado: (2024)

Online Graph Coloring for $k$-Colorable Graphs
por: Kawarabayashi, Ken-ichi, et al.
Publicado: (2025)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
por: Hellmuth, Marc, et al.
Publicado: (2023)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
por: Beisegel, Jesse, et al.
Publicado: (2025)

Solving the List Coloring Problem through a Branch-and-Price algorithm
por: Lucci, Mauro, et al.
Publicado: (2023)

Learning to Prune Instances of Steiner Tree Problem in Graphs
por: Zhang, Jiwei, et al.
Publicado: (2022)

One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming
por: Das, Avinandan
Publicado: (2026)

Exponential Time Approximation for Coloring 3-Colorable Graphs
por: Guruswami, Venkatesan, et al.
Publicado: (2024)

Counting random $k$-SAT near the satisfiability threshold
por: Chen, Zongchen, et al.
Publicado: (2024)

Random local access for sampling k-SAT solutions
por: Dong, Dingding, et al.
Publicado: (2024)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers
por: Beisegel, Jesse, et al.
Publicado: (2025)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
por: Hirahara, Shuichi, et al.
Publicado: (2025)

Approximating Maximum Edge 2-Coloring by Normalizing Graphs
por: Mömke, Tobias, et al.
Publicado: (2024)