Buchumschlag

A Single Exponential-Time FPT Algorithm for Cactus Contraction

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Krithika, R., Misra, Pranabendu, Tale, Prafullkumar
Format:	Preprint
Veröffentlicht:	2025
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

Double Exponential Lower Bound for Telephone Broadcast
von: Tale, Prafullkumar
Veröffentlicht: (2024)

Revisiting Path Contraction and Cycle Contraction
von: Krithika, R., et al.
Veröffentlicht: (2024)

A Finer View of the Parameterized Landscape of Labeled Graph Contractions
von: Mathur, Yashaswini, et al.
Veröffentlicht: (2025)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
von: Krithika, R., et al.
Veröffentlicht: (2023)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
von: Tale, Prafullkumar
Veröffentlicht: (2025)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
von: Bandyapadhyay, Sayan, et al.
Veröffentlicht: (2024)

Revisiting Token Sliding on Chordal Graphs
von: Adak, Rajat, et al.
Veröffentlicht: (2025)

Path Contraction Faster than $2^n$
von: Agrawal, Akanksha, et al.
Veröffentlicht: (2025)

Structural Parameterization of Locating-Dominating Set and Test Cover
von: Chakraborty, Dipayan, et al.
Veröffentlicht: (2024)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
von: Chakraborty, Dipayan, et al.
Veröffentlicht: (2024)

Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and Feedback Vertex Set
von: Akhtar, Sheikh Shakil, et al.
Veröffentlicht: (2025)

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

Space Efficient Algorithms for Parameterised Problems
von: Akhtar, Sheikh Shakil, et al.
Veröffentlicht: (2025)

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
von: Foucaud, Florent, et al.
Veröffentlicht: (2026)

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

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

Parameterized complexity of isometric path partition: treewidth and diameter
von: Chakraborty, Dibyayan, et al.
Veröffentlicht: (2025)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
von: Foucaud, Florent, et al.
Veröffentlicht: (2023)

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

Fast and Practical Single-Exponential Algorithms for Branchwidth
von: Kaneda, Taiki, et al.
Veröffentlicht: (2026)

An FPT algorithm for Matching Cut and d-cut
von: Aravind, N R, et al.
Veröffentlicht: (2021)

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

Improving Order with Queues
von: Karrenbauer, Andreas, et al.
Veröffentlicht: (2022)

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

Online Firefighting on Cactus Graphs
von: Hugen, Max, et al.
Veröffentlicht: (2025)

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)

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)

Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth
von: Liu, Yuxi, et al.
Veröffentlicht: (2026)

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

FPT Constant Approximation Algorithms for Colorful Sum of Radii
von: Liu, Shuilian, 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)

Computing the Center of Uncertain Points on Cactus Graphs
von: Hu, Ran, et al.
Veröffentlicht: (2024)

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

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

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

The Two-Center Problem of Uncertain Points on Cactus Graphs
von: Xu, Haitao, et al.
Veröffentlicht: (2024)

Cactus Representation of Minimum Cuts: Derandomize and Speed up
von: He, Zhongtian, et al.
Veröffentlicht: (2024)