Imagen de Portada

Pseudodeterministic Algorithms for Minimum Cut Problems

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Agarwala, Aryan, Varma, Nithin
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Bipartite Matching is in Catalytic Logspace
por: Agarwala, Aryan, et al.
Publicado: (2025)

Polynomial-Time Pseudodeterministic Construction of Primes
por: Chen, Lijie, et al.
Publicado: (2023)

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

Minimum Stable Cut and Treewidth
por: Lampis, Michael
Publicado: (2021)

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
por: Kenig, Batya
Publicado: (2025)

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

Parameterized Critical Node Cut Revisited
por: Knop, Dušan, et al.
Publicado: (2025)

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

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

Self-referential instances of the dominating set problem are irreducible
por: Zhou, Guangyan
Publicado: (2026)

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
por: Zhang, Bingwei, et al.
Publicado: (2026)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
por: Michel, Lukas, et al.
Publicado: (2023)

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

A tight quasi-polynomial bound for Global Label Min-Cut
por: Jaffke, Lars, et al.
Publicado: (2022)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
por: DeHaan, Ian, et al.
Publicado: (2025)

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

Scheduling Problems with Constrained Rejections
por: Davies, Sami, et al.
Publicado: (2025)

Efficient Catalytic Graph Algorithms
por: Cook, James, et al.
Publicado: (2025)

Improved Algorithm for Permutation Testing
por: Zhang, Xiaojin
Publicado: (2020)

String Consensus Problems with Swaps and Substitutions
por: Gabory, Estéban, et al.
Publicado: (2025)

Equivalent Instances for Scheduling and Packing Problems
por: Jansen, Klaus, et al.
Publicado: (2025)

Neighborhood-Aware Graph Labeling Problem
por: Shahverdikondori, Mohammad, et al.
Publicado: (2026)

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
por: Kratochvíl, Jan, et al.
Publicado: (2020)

Algorithms and Hardness for Estimating Statistical Similarity
por: Bhattacharyya, Arnab, et al.
Publicado: (2025)

Sensitivity Lower Bounds for Approximaiton Algorithms
por: Fleming, Noah, et al.
Publicado: (2024)

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

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
por: Bilò, Davide, et al.
Publicado: (2025)

Complexity of Local Search for Euclidean Clustering Problems
por: Manthey, Bodo, et al.
Publicado: (2023)

NP-Hardness and a PTAS for the Pinwheel Problem
por: Kleinberg, Robert, et al.
Publicado: (2026)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
por: Chudigiewitsch, Florian, et al.
Publicado: (2026)

Semi-Streaming Algorithms for Graph Property Certification
por: Das, Avinandan, et al.
Publicado: (2025)

Exact Algorithms for Distance to Unique Vertex Cover
por: Fioravantes, Foivos, et al.
Publicado: (2025)

Hardness and Algorithmic Results for Roman \{3\}-Domination
por: Reddy, Sangam Balchandar
Publicado: (2025)

Parameterized Algorithms for Editing to Uniform Cluster Graph
por: Gaikwad, Ajinkya, et al.
Publicado: (2024)

No Price Tags? No Problem: Query Strategies for Unpriced Information
por: Nadimpalli, Shivam, et al.
Publicado: (2025)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
por: Nederlof, Jesper
Publicado: (2026)

Structural Parameterizations for Two Bounded Degree Problems Revisited
por: Lampis, Michael, et al.
Publicado: (2023)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
por: Gadekar, Ameet, et al.
Publicado: (2025)

From Amortized to Worst Case Delay in Enumeration Algorithms
por: Capelli, Florent, et al.
Publicado: (2021)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
por: Johnson, Matthew, et al.
Publicado: (2022)