Buchumschlag

An FPT algorithm for Matching Cut and d-cut

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Aravind, N R, Saxena, Roopam
Format:	Preprint
Veröffentlicht:	2021
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Parameterized Complexity of Path Set Packing
von: Aravind, N. R., et al.
Veröffentlicht: (2022)

FPT algorithms over linear delta-matroids with applications
von: Eiben, Eduard, et al.
Veröffentlicht: (2025)

An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
von: Murakami, Hitoshi, et al.
Veröffentlicht: (2024)

FPT Approximations for Connected Maximum Coverage
von: Inamdar, Tanmay, et al.
Veröffentlicht: (2026)

FPT Approximation for Capacitated Sum of Radii
von: Jaiswal, Ragesh, et al.
Veröffentlicht: (2024)

A Single Exponential-Time FPT Algorithm for Cactus Contraction
von: Krithika, R., et al.
Veröffentlicht: (2025)

Optimal FPT-Approximability for Modular Linear Equations
von: Dabrowski, Konrad K., et al.
Veröffentlicht: (2026)

FPT approximations for Capacitated Sum of Radii and Diameters
von: Filtser, Arnold, et al.
Veröffentlicht: (2024)

Improved FPT Approximation for Non-metric TSP
von: Bampis, Evripidis, et al.
Veröffentlicht: (2024)

Minimum+1 Steiner Cuts and Dual Edge Sensitivity Oracle: Bridging the Gap between Global cut and (s,t)-cut
von: Bhanja, Koustav
Veröffentlicht: (2024)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
von: Saxena, Raghuvansh R., et al.
Veröffentlicht: (2024)

Split-or-decompose: Improved FPT branching algorithms for maximum agreement forests
von: Mestel, David, et al.
Veröffentlicht: (2024)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
von: Joseph, et al.
Veröffentlicht: (2023)

FPT Approximations for Fair $k$-Min-Sum-Radii
von: Carta, Lena, et al.
Veröffentlicht: (2024)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
von: Eisenbrand, Friedrich, et al.
Veröffentlicht: (2024)

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
von: Zhou, Jianqi, et al.
Veröffentlicht: (2025)

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
von: Alecu, Bogdan, et al.
Veröffentlicht: (2024)

Matching (Multi)Cut: Algorithms, Complexity, and Enumeration
von: Gomes, Guilherme C. M., et al.
Veröffentlicht: (2024)

FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs
von: Lanzinger, Matthias, et al.
Veröffentlicht: (2023)

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
von: Rohwedder, Lars
Veröffentlicht: (2025)

Pushing the frontiers of subexponential FPT time for Feedback Vertex Set
von: Berthe, Gaétan, et al.
Veröffentlicht: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
von: Dai, Han, et al.
Veröffentlicht: (2025)

FPT Approximations for Fair Sum of Radii with Outliers and General Norm Objectives
von: Gadekar, Ameet
Veröffentlicht: (2026)

FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
von: Jansen, Klaus, et al.
Veröffentlicht: (2024)

Proportionally Fair Matching via Randomized Rounding
von: Duppala, Sharmila, et al.
Veröffentlicht: (2024)

An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange
von: Jansen, Bart M. P., et al.
Veröffentlicht: (2025)

When does FTP become FPT?
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
von: Norose, Ryoma, et al.
Veröffentlicht: (2024)

An approximation algorithm for Maximum DiCut vs. Cut
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
von: Cervenjak, Philip, et al.
Veröffentlicht: (2024)

FPT Parameterisations of Fractional and Generalised Hypertree Width
von: Lanzinger, Matthias, et al.
Veröffentlicht: (2025)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
von: Kolmogorov, Vladimir
Veröffentlicht: (2023)

On the cut-query complexity of approximating max-cut
von: Plevrakis, Orestis, et al.
Veröffentlicht: (2022)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
von: Liu, Shuilian, et al.
Veröffentlicht: (2025)

Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
von: Manurangsi, Pasin
Veröffentlicht: (2024)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)

(Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs
von: Gahlawat, Harmender, et al.
Veröffentlicht: (2025)

Constrained Level Planarity is FPT with Respect to the Vertex Cover Number
von: Klemz, Boris, et al.
Veröffentlicht: (2024)

Simpler O(1) Query Algorithm for Level Ancestors
von: Saxena, Sanjeev
Veröffentlicht: (2022)