Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Wang, Adam
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

(Approximate) Matrix Multiplication via Convolutions
by: Uffenheimer, Yahel, et al.
Published: (2025)

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

On the Parameterized Intractability of Determinant Maximization
by: Ohsaka, Naoto
Published: (2022)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Depth-13 Sorting Networks for 28 Channels
by: Wang, Chengu
Published: (2025)

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

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

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

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

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

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

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

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

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

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

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

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

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

An Approximation Algorithm for Monotone Submodular Cost Allocation
by: Mizutani, Ryuhei
Published: (2025)

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

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

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

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