Buchumschlag

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Georgiadis, Loukas, Kipouridis, Evangelos, Kosinas, Evangelos, Papadopoulos, Charis, Parotsidis, Nikos
Format:	Preprint
Veröffentlicht:	2026
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

On 2-strong connectivity orientations of mixed graphs and related problems
von: Georgiadis, Loukas, et al.
Veröffentlicht: (2023)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
von: Kosinas, Evangelos
Veröffentlicht: (2025)

Faster algorithms for k-Orthogonal Vectors in low dimension
von: Dürr, Anita, et al.
Veröffentlicht: (2025)

Connectivity Oracles for Predictable Vertex Failures
von: Hu, Bingbing, et al.
Veröffentlicht: (2023)

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
von: Korhonen, Tuukka
Veröffentlicht: (2024)

Fitting Tree Metrics and Ultrametrics in Data Streams
von: Carmel, Amir, et al.
Veröffentlicht: (2025)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

Ghost Value Augmentation for $k$-Edge-Connectivity
von: Hershkowitz, D Ellis, et al.
Veröffentlicht: (2023)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
von: Sawettamalya, Pachara, et al.
Veröffentlicht: (2025)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Efficient Contractions of Dynamic Graphs -- with Applications
von: Henzinger, Monika, et al.
Veröffentlicht: (2025)

A Faster Algorithm for Constrained Correlation Clustering
von: Fischer, Nick, et al.
Veröffentlicht: (2025)

Fully Dynamic Strongly Connected Components in Planar Digraphs
von: Karczmarz, Adam, et al.
Veröffentlicht: (2024)

A $2\ell k$ Kernel for $\ell$-Component Order Connectivity
von: Kumar, Mithilesh, et al.
Veröffentlicht: (2016)

A Broader View on Clustering under Cluster-Aware Norm Objectives
von: Herold, Martin G., et al.
Veröffentlicht: (2025)

Clustering to Minimize Cluster-Aware Norm Objectives
von: Herold, Martin G., et al.
Veröffentlicht: (2024)

Streaming Edge Coloring with Subquadratic Palette Size
von: Chechik, Shiri, et al.
Veröffentlicht: (2023)

Almost Tight Additive Guarantees for $k$-Edge-Connectivity
von: Kumar, Nikhil, et al.
Veröffentlicht: (2025)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
von: Goranci, Gramoz, et al.
Veröffentlicht: (2023)

Deterministic Lower Bounds for $k$-Edge Connectivity in the Distributed Sketching Model
von: Robinson, Peter, et al.
Veröffentlicht: (2025)

Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings
von: Biedl, Therese, et al.
Veröffentlicht: (2024)

9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
von: Çivril, Ali
Veröffentlicht: (2024)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
von: Ebbens, Matthijs, et al.
Veröffentlicht: (2024)

Simple Algorithms for Fully Dynamic Edge Connectivity
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

The Connected k-Vertex One-Center Problem on Graphs
von: Zhang, Jingru
Veröffentlicht: (2024)

Connected k-Median with Disjoint and Non-disjoint Clusters
von: Eube, Jan, et al.
Veröffentlicht: (2025)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
von: Çivril, Ali
Veröffentlicht: (2023)

Two-Edge Connectivity via Pac-Man Gluing
von: Garg, Mohit, et al.
Veröffentlicht: (2024)

Fully Dynamic Algorithms for Transitive Reduction
von: Goranci, Gramoz, et al.
Veröffentlicht: (2025)

DynHAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering
von: Yu, Shangdi, et al.
Veröffentlicht: (2025)

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
von: El-Hayek, Antoine, et al.
Veröffentlicht: (2023)

Computing Flows in Subquadratic Space
von: Brand, Jan van den, et al.
Veröffentlicht: (2026)

Dynamic data structures for twin-ordered matrices
von: Bosek, Bartłomiej, et al.
Veröffentlicht: (2026)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2025)

Online Drone Scheduling for Last-mile Delivery
von: Jana, Saswata, et al.
Veröffentlicht: (2024)

An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
von: Kobayashi, Yusuke, et al.
Veröffentlicht: (2026)

A Better-Than-$5/4$-Approximation for Two-Edge Connectivity
von: Hommelsheim, Felix, et al.
Veröffentlicht: (2025)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
von: Long, Yaowei, et al.
Veröffentlicht: (2024)

Dynamic Correlation Clustering in Sublinear Update Time
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)