Imagen de Portada

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Golovach, Petr A., Stamoulis, Giannos, Thilikos, Dimitrios M.
Formato:	Preprint
Publicado:	2022
Materias:	Logic in Computer Science Data Structures and Algorithms Combinatorics 05C83, 05C85, 68R10, 68W01, 68Q19, 03C13, 68Q25, 68Q27 F.2.2; G.2.2; F.4.1
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

Approximating branchwidth on parametric extensions of planarity
por: Thilikos, Dimitrios M., et al.
Publicado: (2023)

A Constant-factor Approximation for Weighted Bond Cover
por: Kim, Eun Jung, et al.
Publicado: (2021)

Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes
por: Sau, Ignasi, et al.
Publicado: (2026)

A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space
por: Bergougnoux, Benjamin, et al.
Publicado: (2025)

ARRIVAL: Recursive Framework & $\ell_1$-Contraction
por: Haslebacher, Sebastian
Publicado: (2025)

Finding irrelevant vertices in linear time on bounded-genus graphs
por: Golovach, Petr A., et al.
Publicado: (2019)

Catching Rats in $H$-minor-free Graphs
por: Gorsky, Maximilian, et al.
Publicado: (2025)

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

Steiner Tree Parameterized by Multiway Cut and Even Less
por: Jansen, Bart M. P., et al.
Publicado: (2024)

On the Average-Case Performance of Greedy for Maximum Coverage
por: Balkanski, Eric, et al.
Publicado: (2026)

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

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
por: Lobe, Elisabeth, et al.
Publicado: (2021)

How quickly can you pack short paths? Engineering a search-tree algorithm for disjoint s-t paths of bounded length
por: Huber, Michael Kiran
Publicado: (2024)

Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds
por: Opris, Andre
Publicado: (2025)

Amnesiac Flooding: Easy to break, hard to escape
por: Austin, Henry, et al.
Publicado: (2025)

Parameterizing the quantification of CMSO: model checking on minor-closed graph classes
por: Sau, Ignasi, et al.
Publicado: (2024)

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

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

Graphs whose vertices of degree at least 2 lie in a triangle
por: Forte, Vinicius L. do, et al.
Publicado: (2022)

Faster parameterized algorithms for modification problems to minor-closed classes
por: Morelle, Laure, et al.
Publicado: (2022)

Optimal Bounds for the k-Disjoint Paths Problem
por: Cavallaro, Dario, et al.
Publicado: (2026)

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

W-state graphs: Structure and Algorithms
por: Gajjala, Rishikesh, et al.
Publicado: (2026)

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

Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
por: Komusiewicz, Christian, et al.
Publicado: (2023)

Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
por: Hommelsheim, Felix
Publicado: (2025)

How to Compute a Moving Sum
por: Maslen, David K., et al.
Publicado: (2025)

Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals
por: Lubiw, Anna, et al.
Publicado: (2025)

Runtime Analyses of NSGA-III on Many-Objective Problems
por: Opris, Andre, et al.
Publicado: (2024)

Achieving Tight $O(4^k)$ Runtime Bounds on Jump$_k$ by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity
por: Opris, Andre, et al.
Publicado: (2024)

A First Runtime Analysis of the PAES-25: An Enhanced Variant of the Pareto Archived Evolution Strategy
por: Opris, Andre
Publicado: (2025)

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

Computing shortest closed curves on non-orientable surfaces
por: Bulavka, Denys, et al.
Publicado: (2024)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
por: Böhnlein, Toni, et al.
Publicado: (2024)

Probabilistic Approach for Detection of High-Frequency Periodic Signals using an Event Camera
por: Ben-Ezra, David El-Chai, et al.
Publicado: (2022)

A $4/3$ Approximation for $2$-Vertex-Connectivity
por: Bosch-Calvo, Miguel, et al.
Publicado: (2023)

Exact Algorithms for MaxCut on Split Graphs
por: Lalovic, Marko
Publicado: (2024)

Extending Exact Integrality Gap Computations for the Metric TSP
por: Cook, William, et al.
Publicado: (2026)

On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
por: Heimann, Sophia, et al.
Publicado: (2026)