Copertina

An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Murakami, Hitoshi, Yamaguchi, Yutaro
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms Combinatorics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
di: Norose, Ryoma, et al.
Pubblicazione: (2024)

Exact Matching in Matrix Multiplication Time
di: Sato, Ryotaro, et al.
Pubblicazione: (2025)

A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices
di: Kano, Takumi, et al.
Pubblicazione: (2026)

Odd and Even Harder Problems on Cycle-Factors
di: Hörsch, Florian, et al.
Pubblicazione: (2025)

Finding Spanning Trees with Perfect Matchings
di: Bérczi, Kristóf, et al.
Pubblicazione: (2024)

Complexity and Algorithm for the Matching vertex-cutset Problem
di: Li, Hengzhe, et al.
Pubblicazione: (2025)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
di: Eisenbrand, Friedrich, et al.
Pubblicazione: (2024)

A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching
di: Izumi, Taisuke, et al.
Pubblicazione: (2023)

Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
di: Haviv, Ishay
Pubblicazione: (2022)

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

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
di: Hellmuth, Marc, et al.
Pubblicazione: (2023)

Forgetting Alternation and Blossoms: A New Framework for Fast Matching Augmentation and Its Applications to Sequential/Distributed/Streaming Computation
di: Izumi, Taisuke, et al.
Pubblicazione: (2025)

Matroid Intersection under Minimum Rank Oracle
di: Bárász, Mihály, et al.
Pubblicazione: (2024)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
di: Dai, Han, et al.
Pubblicazione: (2025)

Rainbow Arborescence Conjecture
di: Bérczi, Kristóf, et al.
Pubblicazione: (2024)

Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension
di: Bartier, Valentin, et al.
Pubblicazione: (2023)

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
di: Alecu, Bogdan, et al.
Pubblicazione: (2024)

On the Two Paths Theorem and the Two Disjoint Paths Problem
di: Humeau, Samuel, et al.
Pubblicazione: (2025)

A Maximum Linear Arrangement Problem on Directed Graphs
di: DeVos, Matt, et al.
Pubblicazione: (2018)

Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems
di: Bampis, Evripidis, et al.
Pubblicazione: (2024)

Complexity Gaps between Point and Interval Temporal Graphs for some Reachability Problems
di: Aubian, Guillaume, et al.
Pubblicazione: (2025)

Optimising Cylindrical Algebraic Coverings for use in SMT by Solving a Set Covering Problem with Reasons
di: Babatunde, Abiola, et al.
Pubblicazione: (2026)

Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems
di: Gribanov, Dmitry, et al.
Pubblicazione: (2022)

Paths and Intersections: Exact Emulators for Planar Graphs
di: Li, George Z., et al.
Pubblicazione: (2025)

An Exact Algorithm for the Unanimous Vote Problem
di: Keles, Feyza Duman, et al.
Pubblicazione: (2025)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
di: Bartlmae, Simon, et al.
Pubblicazione: (2024)

A refined graph container lemma and applications to the hard-core model on bipartite expanders
di: Jenssen, Matthew, et al.
Pubblicazione: (2024)

Computational Complexity of Swish
di: Horiyama, Takashi, et al.
Pubblicazione: (2026)

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

Space Efficient Algorithms for Parameterised Problems
di: Akhtar, Sheikh Shakil, et al.
Pubblicazione: (2025)

Algorithmic Cluster Expansions for Quantum Problems
di: Mann, Ryan L., et al.
Pubblicazione: (2023)

An FPT algorithm for Matching Cut and d-cut
di: Aravind, N R, et al.
Pubblicazione: (2021)

The Strong Birthday Problem Revisited
di: Tripathy, Chijul B.
Pubblicazione: (2025)

Solving a Random Asymmetric TSP Exactly in Quasi-Polynomial Time w.h.p
di: Bell, Tolson, et al.
Pubblicazione: (2023)

Algorithmic Reductions: Network Flow and NP-Completeness in Real-World Scheduling Problems
di: Sinhal, Anay, et al.
Pubblicazione: (2026)

A Fixed-Parameter Algorithm for the Kneser Problem
di: Haviv, Ishay
Pubblicazione: (2022)

Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations
di: Hathcock, Daniel, et al.
Pubblicazione: (2025)

Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz--Parisi Potential
di: Koehler, Frederic, et al.
Pubblicazione: (2025)

Problems on Group-labeled Matroid Bases
di: Hörsch, Florian, et al.
Pubblicazione: (2024)

Kernelization Complexity of Solution Discovery Problems
di: Grobler, Mario, et al.
Pubblicazione: (2024)