Cover Image

Faster Algorithm for Second (s,t)-mincut and Breaking Quadratic barrier for Dual Edge Sensitivity for (s,t)-mincut

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Baswana, Surender, Bhanja, Koustav, Roy, Anupam
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Vital Edges for (s,t)-mincut: Efficient Algorithms, Compact Structures, and Optimal Sensitivity Oracle
by: Baswana, Surender, et al.
Published: (2023)

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

Optimal Sensitivity Oracle for Steiner Mincut
by: Bhanja, Koustav
Published: (2024)

The connectivity carcass of a vertex subset in a graph: both odd and even case
by: Baswana, Surender, et al.
Published: (2025)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
by: Bhanja, Koustav, et al.
Published: (2025)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
by: Assadi, Sepehr
Published: (2024)

Faster Algorithms for Dual-Failure Replacement Paths
by: Chechik, Shiri, et al.
Published: (2024)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2024)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Faster Edge Coloring by Partition Sieving
by: Akmal, Shyan, et al.
Published: (2025)

Simple and Faster Algorithms for Knapsack
by: He, Qizheng, et al.
Published: (2023)

Faster Algorithms for Graph Monopolarity
by: Philip, Geevarghese, et al.
Published: (2024)

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

Faster Algorithms for Longest Common Substring
by: Charalampopoulos, Panagiotis, et al.
Published: (2021)

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
by: Cohen, Edith, et al.
Published: (2025)

A Faster Algorithm for Constrained Correlation Clustering
by: Fischer, Nick, et al.
Published: (2025)

Faster Algorithms for Shortest Unique or Absent Substrings
by: Charalampopoulos, Panagiotis, et al.
Published: (2026)

Faster Algorithms for Text-to-Pattern Hamming Distances
by: Chan, Timothy M., et al.
Published: (2023)

Faster Algorithm for Structured John Ellipsoid Computation
by: Cao, Yang, et al.
Published: (2022)

A Faster Algorithm for Pigeonhole Equal Sums
by: Jin, Ce, et al.
Published: (2024)

ExpoSort: Breaking the quasi-polynomial-time barrier for reluctant sorting
by: Abrahamsen, Mikkel
Published: (2024)

Faster Algorithms for Schatten-p Low Rank Approximation
by: Kacham, Praneeth, et al.
Published: (2024)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
by: Bukov, Anton, et al.
Published: (2023)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
by: Kadria, Avi, et al.
Published: (2025)

Faster Approximation Algorithms for k-Center via Data Reduction
by: Filtser, Arnold, et al.
Published: (2025)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
by: Łącki, Jakub, et al.
Published: (2025)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
by: Chuzhoy, Julia, et al.
Published: (2026)

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
by: Kwok, Shawxing
Published: (2025)

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
by: Kociumaka, Tomasz, et al.
Published: (2025)

A Faster Deterministic Algorithm for Kidney Exchange via Representative Set
by: Tian, Kangyi, et al.
Published: (2026)

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
by: Alman, Josh, et al.
Published: (2024)

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments
by: Kumar, Mithilesh, et al.
Published: (2024)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
by: Bhattacharya, Sayan, et al.
Published: (2024)

Engineering Edge Orientation Algorithms
by: Reinstädtler, H., et al.
Published: (2024)

Risk-Sensitive Online Algorithms
by: Christianson, Nicolas, 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)

Faster Fixed Parameter Tractable Algorithms for Counting Markov Equivalence Classes with Special Skeletons
by: Sharma, Vidya Sagar
Published: (2023)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
by: Jin, Ce, et al.
Published: (2024)

Faster Relational Algorithms Using Geometric Data Structures
by: Esmailpour, Aryan, et al.
Published: (2026)