Imagen de Portada

Determining Implication of Fixed Matrix Prenex Normal Forms Can Be Decided in Linear Time

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Wang, Adam
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms Discrete Mathematics
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Detecting Disjoint Shortest Paths in Linear Time and More
por: Akmal, Shyan, et al.
Publicado: (2024)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
por: Paul-Pena, Daniel, et al.
Publicado: (2022)

(Approximate) Matrix Multiplication via Convolutions
por: Uffenheimer, Yahel, et al.
Publicado: (2025)

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

On the Parameterized Intractability of Determinant Maximization
por: Ohsaka, Naoto
Publicado: (2022)

On the Relationship Between Several Variants of the Linear Hashing Conjecture
por: Westover, Alek
Publicado: (2023)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
por: Bourneuf, Romain, et al.
Publicado: (2025)

Double-Ended Palindromic Trees in Linear Time
por: Wang, Qisheng, et al.
Publicado: (2022)

Hypergraph Connectivity Augmentation in Strongly Polynomial Time
por: Bérczi, Kristóf, et al.
Publicado: (2024)

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

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
por: Paul-Pena, Daniel, et al.
Publicado: (2024)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
por: Ghanbari, Babak, et al.
Publicado: (2026)

Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
por: Marin, Malory
Publicado: (2025)

DRESS and the WL Hierarchy: Climbing One Deletion at a Time
por: Velilla, Eduar Castrillo
Publicado: (2026)

Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
por: Soulignac, Francisco J.
Publicado: (2025)

Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches
por: Jordon, Addie, et al.
Publicado: (2025)

Space-Efficient Hierholzer: Eulerian Cycles in $\mathrm{O}(m)$ Time and $\mathrm{O}(n)$ Space
por: Alaoui, Ziad Ismaili, et al.
Publicado: (2025)

Fanciful Figurines flip Free Flood-It -- Polynomial-Time Miniature Painting on Co-gem-free Graphs
por: Rosenke, Christian, et al.
Publicado: (2026)

Matrix Scaling: a New Heuristic for the Feedback Vertex Set Problem
por: Shook, James M., et al.
Publicado: (2025)

On The Maximum Linear Arrangement Problem for Trees
por: Alemany-Puig, Lluís, et al.
Publicado: (2023)

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
por: Paschalidis, Phevos, et al.
Publicado: (2023)

Depth-13 Sorting Networks for 28 Channels
por: Wang, Chengu
Publicado: (2025)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
por: Wang, Chen, et al.
Publicado: (2024)

Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
por: Lill, Jonas, et al.
Publicado: (2024)

Correcting matrix products over the ring of integers
por: Wu, Yu-Lun, et al.
Publicado: (2023)

An algorithm with a delay of $\mathcal{O}(kΔ)$ for enumerating connected induced subgraphs of size $k$
por: Xiao, Chenglong, et al.
Publicado: (2024)

Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
por: Ameli, Afrouz Jabal, et al.
Publicado: (2026)

Approximately covering vertices by order-$5$ or longer paths
por: Gong, Mingyang, et al.
Publicado: (2024)

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

Sampling Balanced Forests of Grids in Polynomial Time
por: Cannon, Sarah, et al.
Publicado: (2023)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
por: Bourneuf, Romain, et al.
Publicado: (2025)

Average-Case Matrix Discrepancy: Asymptotics and Online Algorithms
por: Kunisky, Dmitriy, et al.
Publicado: (2023)

String Matching with a Dynamic Pattern
por: Monteiro, Bruno, et al.
Publicado: (2025)

Inverse matroid optimization under subset constraints
por: Bérczi, Kristóf, et al.
Publicado: (2025)

Graph Coloring Below Guarantees via Co-Triangle Packing
por: Akmal, Shyan, et al.
Publicado: (2025)

An Approximation Algorithm for Monotone Submodular Cost Allocation
por: Mizutani, Ryuhei
Publicado: (2025)

Greedy Algorithms for Shortcut Sets and Hopsets
por: Bals, Ben, et al.
Publicado: (2025)

Approximating Submodular Matroid-Constrained Partitioning
por: Bérczi, Kristóf, et al.
Publicado: (2025)

A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering
por: Veldt, Nate
Publicado: (2025)

UAIC_Twin_Width: An Exact yet Efficient Twin-Width Algorithm
por: Arhire, Andrei, et al.
Publicado: (2025)