Buchumschlag

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

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Wang, Adam
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Discrete Mathematics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Detecting Disjoint Shortest Paths in Linear Time and More
von: Akmal, Shyan, et al.
Veröffentlicht: (2024)

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

(Approximate) Matrix Multiplication via Convolutions
von: Uffenheimer, Yahel, et al.
Veröffentlicht: (2025)

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

On the Parameterized Intractability of Determinant Maximization
von: Ohsaka, Naoto
Veröffentlicht: (2022)

On the Relationship Between Several Variants of the Linear Hashing Conjecture
von: Westover, Alek
Veröffentlicht: (2023)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
von: Bourneuf, Romain, et al.
Veröffentlicht: (2025)

Double-Ended Palindromic Trees in Linear Time
von: Wang, Qisheng, et al.
Veröffentlicht: (2022)

Hypergraph Connectivity Augmentation in Strongly Polynomial Time
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

Exponential Time Approximation for Coloring 3-Colorable Graphs
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
von: Paul-Pena, Daniel, et al.
Veröffentlicht: (2024)

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

Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
von: Marin, Malory
Veröffentlicht: (2025)

DRESS and the WL Hierarchy: Climbing One Deletion at a Time
von: Velilla, Eduar Castrillo
Veröffentlicht: (2026)

Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
von: Soulignac, Francisco J.
Veröffentlicht: (2025)

Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches
von: Jordon, Addie, et al.
Veröffentlicht: (2025)

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

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

Matrix Scaling: a New Heuristic for the Feedback Vertex Set Problem
von: Shook, James M., et al.
Veröffentlicht: (2025)

On The Maximum Linear Arrangement Problem for Trees
von: Alemany-Puig, Lluís, et al.
Veröffentlicht: (2023)

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
von: Paschalidis, Phevos, et al.
Veröffentlicht: (2023)

Depth-13 Sorting Networks for 28 Channels
von: Wang, Chengu
Veröffentlicht: (2025)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
von: Wang, Chen, et al.
Veröffentlicht: (2024)

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

Correcting matrix products over the ring of integers
von: Wu, Yu-Lun, et al.
Veröffentlicht: (2023)

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

Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
von: Ameli, Afrouz Jabal, et al.
Veröffentlicht: (2026)

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

Counting random $k$-SAT near the satisfiability threshold
von: Chen, Zongchen, et al.
Veröffentlicht: (2024)

Sampling Balanced Forests of Grids in Polynomial Time
von: Cannon, Sarah, et al.
Veröffentlicht: (2023)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
von: Bourneuf, Romain, et al.
Veröffentlicht: (2025)

Average-Case Matrix Discrepancy: Asymptotics and Online Algorithms
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2023)

String Matching with a Dynamic Pattern
von: Monteiro, Bruno, et al.
Veröffentlicht: (2025)

Inverse matroid optimization under subset constraints
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

Graph Coloring Below Guarantees via Co-Triangle Packing
von: Akmal, Shyan, et al.
Veröffentlicht: (2025)

An Approximation Algorithm for Monotone Submodular Cost Allocation
von: Mizutani, Ryuhei
Veröffentlicht: (2025)

Greedy Algorithms for Shortcut Sets and Hopsets
von: Bals, Ben, et al.
Veröffentlicht: (2025)

Approximating Submodular Matroid-Constrained Partitioning
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering
von: Veldt, Nate
Veröffentlicht: (2025)

UAIC_Twin_Width: An Exact yet Efficient Twin-Width Algorithm
von: Arhire, Andrei, et al.
Veröffentlicht: (2025)