Copertina

Inapproximability of Counting Permutation Patterns

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Opler, Michal
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
di: Opler, Michal
Pubblicazione: (2024)

Compact representations of pattern-avoiding permutations
di: Kozma, László, et al.
Pubblicazione: (2025)

Counting Permutation Patterns with Multidimensional Trees
di: Beniamini, Gal, et al.
Pubblicazione: (2024)

Optimization with pattern-avoiding input
di: Berendsohn, Benjamin Aram, et al.
Pubblicazione: (2023)

Pathfinding in Self-Deleting Graphs
di: Dvořák, Michal, et al.
Pubblicazione: (2025)

Fast and simple multiplication of bounded twin-width matrices
di: Kozma, László, et al.
Pubblicazione: (2026)

Precoloring extension with demands on paths
di: Das, Arun Kumar, et al.
Pubblicazione: (2025)

Exact Algorithms for Distance to Unique Vertex Cover
di: Fioravantes, Foivos, et al.
Pubblicazione: (2025)

Treedepth Inapproximability and Exponential ETH Lower Bound
di: Bonnet, Édouard, et al.
Pubblicazione: (2025)

Counting Patterns in Degenerate Graphs in Constant Space
di: Komarath, Balagopal, et al.
Pubblicazione: (2025)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
di: Bilò, Davide, et al.
Pubblicazione: (2024)

Contextual Pattern Mining and Counting
di: Li, Ling, et al.
Pubblicazione: (2025)

Permutation patterns in streams
di: Berendsohn, Benjamin Aram
Pubblicazione: (2025)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
di: Frei, Fabian, et al.
Pubblicazione: (2025)

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
di: Fischer, Nick, et al.
Pubblicazione: (2024)

Superconstant Inapproximability of Decision Tree Learning
di: Koch, Caleb, et al.
Pubblicazione: (2024)

Tight Inapproximability of Target Set Reconfiguration
di: Ohsaka, Naoto
Pubblicazione: (2024)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2023)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
di: S., Karthik C., et al.
Pubblicazione: (2024)

Greedy BST on Permutation Initial Tree
di: Pareek, Akash
Pubblicazione: (2024)

Optimal Distance Labeling for Permutation Graphs
di: Gawrychowski, Paweł, et al.
Pubblicazione: (2024)

Inapproximability of Maximum Diameter Clustering for Few Clusters
di: Fleischmann, Henry, et al.
Pubblicazione: (2023)

Succinct Data Structures for Baxter Permutation and Related Families
di: Chakraborty, Sankardeep, et al.
Pubblicazione: (2024)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
di: Hirahara, Shuichi, et al.
Pubblicazione: (2023)

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

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
di: Hirahara, Shuichi, et al.
Pubblicazione: (2024)

Bounding the Average Move Structure Query for Faster and Smaller RLBWT Permutations
di: Brown, Nathaniel K., et al.
Pubblicazione: (2026)

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
di: Bampis, Evripidis, et al.
Pubblicazione: (2025)

Multi-dimensional Approximate Counting
di: Wang, Dingyu
Pubblicazione: (2024)

Fast Approximate Counting of Cycles
di: Censor-Hillel, Keren, et al.
Pubblicazione: (2024)

Counting Cohesive Subgraphs with Hereditary Properties
di: Li, Rong-Hua, et al.
Pubblicazione: (2024)

Counting distinct (non-)crossing substrings
di: Umezaki, Haruki, et al.
Pubblicazione: (2025)

Counting on General Run-Length Grammars
di: Navarro, Gonzalo, et al.
Pubblicazione: (2024)

Where to Split and When to Charge: Optimal Route Construction from Customer Permutations in Electric Vehicle Routing
di: Uroić, Leon Stjepan, et al.
Pubblicazione: (2026)

Approximately Counting Knapsack Solutions in Subquadratic Time
di: Feng, Weiming, et al.
Pubblicazione: (2024)

Cover Edge-Based Novel Triangle Counting
di: Bader, David A., et al.
Pubblicazione: (2024)

Counting perfect matchings and Hamiltonian cycles faster
di: Li, Baitian
Pubblicazione: (2023)

Counting Distinct Square Substrings in Sublinear Time
di: Charalampopoulos, Panagiotis, et al.
Pubblicazione: (2025)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
di: Pilipczuk, Michał, et al.
Pubblicazione: (2025)

Exact Sampling of Permutations with a Fixed Longest Increasing Subsequence
di: Clifford, Peter, et al.
Pubblicazione: (2026)