:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Khalife, Sammy, Ponty, Yann, Bulteau, Laurent
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Computational Complexity Computation and Language
Online Access:	https://arxiv.org/abs/2402.08830
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

String Consensus Problems with Swaps and Substitutions
by: Gabory, Estéban, et al.
Published: (2025)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Enumerating models of DNF faster: breaking the dependency on the formula size
by: Capelli, Florent, et al.
Published: (2018)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

From Amortized to Worst Case Delay in Enumeration Algorithms
by: Capelli, Florent, et al.
Published: (2021)

Isometric path complexity of graphs
by: Chakraborty, Dibyayan, et al.
Published: (2022)

Gray Codes With Constant Delay and Constant Auxiliary Space
by: Amarilli, Antoine, et al.
Published: (2026)

Parameterized Restless Temporal Path
by: Cauvi, Justine, et al.
Published: (2025)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
by: Huang, Neng, et al.
Published: (2024)

The complexity of testing all properties of planar graphs, and the role of isomorphism
by: Basu, Sabyasachi, et al.
Published: (2021)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
by: Ducoffe, Guillaume
Published: (2026)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
by: Dumas, Maël, et al.
Published: (2022)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
by: Kluk, Kacper, et al.
Published: (2025)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
by: Esmer, Barış Can, et al.
Published: (2022)

Complexity of Finding and Enumerating Interconnection Trees
by: Demange, Noé, et al.
Published: (2026)

Smoothed analysis for graph isomorphism
by: Anastos, Michael, et al.
Published: (2024)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
by: Alman, Josh, et al.
Published: (2024)

On the complexity of global Roman domination problem in graphs
by: Reddy, Sangam Balchandar, et al.
Published: (2026)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
by: Leake, Jonathan, et al.
Published: (2025)

An unconditional lower bound for the active-set method on the hypercube
by: Disser, Yann, et al.
Published: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
by: Kunisky, Dmitriy, et al.
Published: (2024)

A faster FPRAS for #NFA
by: Meel, Kuldeep S., et al.
Published: (2023)

Maximum $k$- vs. $\ell$-colourings of graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2023)

Finding Diverse Strings and Longest Common Subsequences in a Graph
by: Shida, Yuto, et al.
Published: (2024)

Hardness of Regular Expression Matching with Extensions
by: Nogami, Taisei, et al.
Published: (2026)

Symbolic Functional Decomposition: A Reconfiguration Approach
by: Oliveira, Mateus de Oliveira, et al.
Published: (2026)

The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
by: Bringmann, Karl, et al.
Published: (2023)

Channel allocation revisited through 1-extendability of graphs
by: Busson, Anthony, et al.
Published: (2024)

A note on approximating the average degree of bounded arboricity graphs
by: Eden, Talya, et al.
Published: (2026)

On Classifying Continuous Constraint Satisfaction Problems
by: Miltzow, Tillmann, et al.
Published: (2021)

An unconditional lower bound for the active-set method in convex quadratic maximization
by: Bach, Eleon, et al.
Published: (2025)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
by: Johnson, Matthew, et al.
Published: (2022)

Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs
by: Kutner, David C., et al.
Published: (2025)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
by: Apers, Simon, et al.
Published: (2021)

Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes
by: Chauhan, Archit, et al.
Published: (2025)

Can You Link Up With Treewidth?
by: Curticapean, Radu, et al.
Published: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Simple approximation algorithms for Polyamorous Scheduling
by: Biktairov, Yuriy, et al.
Published: (2024)

Size Minimization For Multi-Output AND-Functions
by: Armbruster, Susanne
Published: (2024)

TSP Escapes the $O(2^n n^2)$ Curse
by: Stoian, Mihail
Published: (2024)