:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Watel, Dimitri, Weisser, Marc-Antoine, Barth, Dominique, Aboulfath, Ylène, Mautor, Thierry
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2404.17223
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Maximal Line Digraphs
by: Japhet, Quentin, et al.
Published: (2024)

Maximal Line Digraphs
by: Quentin Japhet, et al.
Published: (2026)

Linear Matroid Intersection is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

On Minimum Maximal Distance-k Matchings
by: Kartynnik, Yury, et al.
Published: (2016)

Inverse Intersections for Boolean Satisfiability Problems
by: Homer, Paul W.
Published: (2025)

Are Depth-2 Regular Expressions Hard to Intersect?
by: Ascone, Rocco, et al.
Published: (2025)

Minimum cost flow decomposition on arc-coloured networks
by: Neto, Claudio Carvalho, et al.
Published: (2025)

Partial Minimum Branching Program Size Problem is ETH-hard
by: Glinskih, Ludmila, et al.
Published: (2024)

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
by: Bhattiprolu, Vijay, et al.
Published: (2025)

Minimum Selective Subset on Some Graph Classes
by: Manna, Bubai
Published: (2025)

One-way Communication Complexity of Minimum Vertex Cover in General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
by: Adriaens, Florian, et al.
Published: (2024)

Temporal Cycle Detection and Acyclic Temporization
by: de Andrade, Davi, et al.
Published: (2025)

Minimum Selective Subset on Unit Disk Graphs and Circle Graphs
by: Manna, Bubai
Published: (2025)

Logical Expressibility of Syntactic NL for Complementarity, Monotonicity, and Maximization
by: Yamakami, Tomoyuki
Published: (2024)

Minimum Stable Cut and Treewidth
by: Lampis, Michael
Published: (2021)

The Complexity of Contracting Bipartite Graphs into Small Cycles
by: Krithika, R., et al.
Published: (2022)

Proportionally dense subgraphs of maximum size in degree-constrained graphs
by: Baghirova, Narmina, et al.
Published: (2024)

Maximizing Phylogenetic Diversity under Time Pressure: Planning with Extinctions Ahead
by: Jones, Mark, et al.
Published: (2024)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

Envy-Free House Allocation with Minimum Subsidy
by: Choo, Davin, et al.
Published: (2024)

Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study
by: Komusiewicz, Christian, et al.
Published: (2024)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2022)

Equations over Finite Monoids with Infinite Promises
by: Larrauri, Alberto, et al.
Published: (2025)

Indefiniteness makes lattice reduction easier
by: Joux, Antoine
Published: (2025)

On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes
by: Drucker, Andrew, et al.
Published: (2024)

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

Finding Minimum Matching Cuts in $H$-free Graphs
by: Lucke, Felicia, et al.
Published: (2025)

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
by: Upirvitskiy, Aleksey, et al.
Published: (2026)

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
by: Gaikwad, Ajinkya, et al.
Published: (2025)

Maximization of Approximately Submodular Functions
by: Horel, Thibaut, et al.
Published: (2024)

Improved Hardness Results for Learning Intersections of Halfspaces
by: Tiegel, Stefan
Published: (2024)

The Complexity of Maximal Common Subsequence Enumeration
by: Buzzega, Giovanni, et al.
Published: (2025)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
by: Gholizadeh, Hossein, et al.
Published: (2025)

Disrupting Bipartite Trading Networks: Matching for Revenue Maximization
by: D'Amico-Wong, Luca, et al.
Published: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
by: Stoian, Mihail
Published: (2024)

A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
by: Li, Zhengyu, et al.
Published: (2023)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
by: Dhar, Anubhav, et al.
Published: (2025)

Submodular Maximization under Supermodular Constraint: Greedy Guarantees
by: Srivastava, Ajitesh, et al.
Published: (2026)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)