Image de couverture de livre

A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Bringmann, Karl, Gorbachev, Egor
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
par: Gorbachev, Egor, et autres
Publié: (2024)

Efficiently Listing Projected Trees, and Equivalence of Listing and Enumeration
par: Bringmann, Karl, et autres
Publié: (2026)

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
par: Gawrychowski, Paweł, et autres
Publié: (2024)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
par: Boneh, Itai, et autres
Publié: (2025)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
par: Paul-Pena, Daniel, et autres
Publié: (2024)

Knapsack with Small Items in Near-Quadratic Time
par: Bringmann, Karl
Publié: (2023)

A Subquadratic Bound for Online Bisection
par: Bienkowski, Marcin, et autres
Publié: (2023)

Computing Flows in Subquadratic Space
par: Brand, Jan van den, et autres
Publié: (2026)

Weakly Approximating Knapsack in Subquadratic Time
par: Chen, Lin, et autres
Publié: (2025)

Engineering Dominating Patterns: A Fine-grained Case Study
par: Dransfeld, Jonathan, et autres
Publié: (2025)

Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
par: Bringmann, Karl, et autres
Publié: (2022)

Approximately Counting Knapsack Solutions in Subquadratic Time
par: Feng, Weiming, et autres
Publié: (2024)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
par: Bilò, Davide, et autres
Publié: (2024)

Streaming Edge Coloring with Subquadratic Palette Size
par: Chechik, Shiri, et autres
Publié: (2023)

Approximate Distance Sensitivity Oracles in Subquadratic Space
par: Bilò, Davide, et autres
Publié: (2023)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
par: Bringmann, Karl, et autres
Publié: (2024)

Beating Bellman's Algorithm for Subset Sum
par: Bringmann, Karl, et autres
Publié: (2024)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
par: Bringmann, Karl, et autres
Publié: (2026)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
par: Bathie, Gabriel, et autres
Publié: (2025)

Subquadratic Submodular Maximization with a General Matroid Constraint
par: Kobayashi, Yusuke, et autres
Publié: (2024)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
par: Kirkpatrick, Yael, et autres
Publié: (2026)

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
par: Bille, Philip, et autres
Publié: (2022)

Near-Optimal Directed Low-Diameter Decompositions
par: Bringmann, Karl, et autres
Publié: (2025)

Lawler-Moore Speedups via Additive Combinatorics
par: Bringmann, Karl, et autres
Publié: (2026)

Subquadratic Counting via Perfect Marginal Sampling
par: Chen, Xiaoyu, et autres
Publié: (2026)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
par: Anand, Aditya, et autres
Publié: (2024)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
par: Mao, Xiao, et autres
Publié: (2026)

Fréchet Distance in Subquadratic Time
par: Cheng, Siu-Wing, et autres
Publié: (2024)

Polyline Simplification has Cubic Complexity
par: Bringmann, Karl, et autres
Publié: (2018)

Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more
par: Karczmarz, Adam, et autres
Publié: (2024)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
par: Georgiadis, Loukas, et autres
Publié: (2026)

Fine-Grained Classification Of Detecting Dominating Patterns
par: Dransfeld, Jonathan, et autres
Publié: (2025)

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
par: Cheng, Siu-Wing, et autres
Publié: (2025)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
par: Çivril, Ali
Publié: (2023)

Destroying Densest Subgraphs is Hard
par: Bazgan, Cristina, et autres
Publié: (2024)

Finding Order-Preserving Subgraphs
par: Imamura, Haruya, et autres
Publié: (2025)

Forbidden Subgraph Problems with Predictions
par: Böckenhauer, Hans-Joachim, et autres
Publié: (2025)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
par: Ebbens, Matthijs, et autres
Publié: (2024)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
par: Gholizadeh, Hossein, et autres
Publié: (2025)

Counting Cohesive Subgraphs with Hereditary Properties
par: Li, Rong-Hua, et autres
Publié: (2024)