Cover Image

A Survey on Graph Problems Parameterized Above and Below Guaranteed Values

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gutin, Gregory, Mnich, Matthias
Format:	Preprint
Published:	2022
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
by: Bergougnoux, Benjamin, et al.
Published: (2023)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
by: Wang, Chen, et al.
Published: (2024)

A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
by: Armbruster, Susanne, et al.
Published: (2024)

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
by: Fischer, David, et al.
Published: (2022)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
by: Chalermsook, Parinya, et al.
Published: (2021)

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
by: Kaul, Matthias, et al.
Published: (2025)

Graph Coloring Below Guarantees via Co-Triangle Packing
by: Akmal, Shyan, et al.
Published: (2025)

A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
by: Bentert, Matthias, et al.
Published: (2026)

Above-Guarantee Algorithm for Properly Colored Spanning Trees
by: Bai, Yuhang, et al.
Published: (2026)

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
by: Kaul, Matthias, et al.
Published: (2024)

Parameterized Algorithms for the Drone Delivery Problem
by: Bartlmae, Simon, et al.
Published: (2026)

Dynamic Parameterized Feedback Problems in Tournaments
by: Zych-Pawlewicz, Anna, et al.
Published: (2024)

Generalized Graph Packing Problems Parameterized by Treewidth
by: Esmer, Barış Can, et al.
Published: (2025)

Parameterized Quantum Query Algorithms for Graph Problems
by: Terao, Tatsuya, et al.
Published: (2024)

The Parameterized Complexity Landscape of the Unsplittable Flow Problem
by: Ganian, Robert, et al.
Published: (2024)

Parameterized Complexity of Simultaneous Planarity
by: Fink, Simon D., et al.
Published: (2023)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
by: Liu, Shuilian, et al.
Published: (2025)

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
by: Eiben, Eduard, et al.
Published: (2024)

Parameterized Algorithms for the Steiner Arborescence Problem on a Hypercube
by: Mahapatra, Sugyani, et al.
Published: (2021)

Structural Parameterizations of the Biclique-Free Vertex Deletion Problem
by: Goldmann, Lito, et al.
Published: (2023)

New Approximation Guarantees for The Inventory Staggering Problem
by: Alon, Noga, et al.
Published: (2025)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
by: Zhao, Jingyang, et al.
Published: (2025)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
by: Feldmann, Andreas Emil, et al.
Published: (2024)

Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
by: Goyal, Dishant, et al.
Published: (2024)

Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
by: Bentert, Matthias, et al.
Published: (2024)

Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
by: Lill, Jonas, et al.
Published: (2024)

Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
by: Esmer, Barış Can, et al.
Published: (2024)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
by: Khanna, Sanjeev, et al.
Published: (2026)

Approximate Graph Propagation Revisited: Dynamic Parameterized Queries, Tighter Bounds and Dynamic Updates
by: Zhao, Zhuowei, et al.
Published: (2025)

Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy
by: Pfisterer, Kevin, et al.
Published: (2026)

Parameterizing Path Partitions
by: Fernau, Henning, et al.
Published: (2022)

Local Max-Cut on Sparse Graphs
by: Schwartzman, Gregory
Published: (2023)

The Parameterized Landscape of Labeled Graph Contractions
by: Lafond, Manuel, et al.
Published: (2025)

Parameterized algorithms for $k$-Inversion
by: Antony, Dhanyamol, et al.
Published: (2026)

Structural Parameterizations of Vertex Integrity
by: Gima, Tatsuya, et al.
Published: (2023)

Parameterized Complexity of Efficient Sortation
by: Ganian, Robert, et al.
Published: (2024)

Structural Parameterizations of $k$-Planarity
by: Gima, Tatsuya, et al.
Published: (2025)

Faster Parameterized Vertex Multicut
by: Chu, Huairui, et al.
Published: (2026)

Near-real-time Solutions for Online String Problems
by: Köppl, Dominik, et al.
Published: (2026)

Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
by: Dhulipala, Laxman, et al.
Published: (2025)