Buchumschlag

Online Disjoint Spanning Trees and Polymatroid Bases

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chandrasekaran, Karthekeyan, Chekuri, Chandra, Zhu, Weihao
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

Hedgegraph Polymatroids
von: Chandrasekaran, Karthekeyan, et al.
Veröffentlicht: (2025)

On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions
von: Chandrasekaran, Karthekeyan, et al.
Veröffentlicht: (2025)

Hypergraph Splitting-Off via Element-Connectivity Preserving Reductions
von: Chandrasekaran, Karthekeyan, et al.
Veröffentlicht: (2025)

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

On Sparsest Cut and Conductance in Directed Polymatroidal Networks
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
von: Chandrasekaran, Karthekeyan, et al.
Veröffentlicht: (2023)

Uncrossed Multiflows and Applications to Disjoint Paths
von: Chekuri, Chandra, et al.
Veröffentlicht: (2025)

Monotone Submodular Multiway Partition
von: Bi, Richard, et al.
Veröffentlicht: (2024)

Approximation Algorithms for Network Design in Non-Uniform Fault Models
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Approximation Algorithms for Hop Constrained and Buy-at-Bulk Network Design via Hop Constrained Oblivious Routing
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Colorful Priority $k$-Supplier
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Node-Weighted Multicut in Planar Digraphs
von: Chekuri, Chandra, et al.
Veröffentlicht: (2026)

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

$\{s,t\}$-Separating Principal Partition Sequence of Submodular Functions
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations
von: Chandrasekaran, Karthekeyan, et al.
Veröffentlicht: (2025)

Hypergraph Connectivity Augmentation in Strongly Polynomial Time
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

Splitting-off in Hypergraphs
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2023)

Streaming Algorithms for Network Design
von: Chekuri, Chandra, et al.
Veröffentlicht: (2025)

Approximating Submodular Matroid-Constrained Partitioning
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

Online Disjoint Set Covers: Randomization is not Necessary
von: Bienkowski, Marcin, et al.
Veröffentlicht: (2024)

Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems
von: Harb, Elfarouk, et al.
Veröffentlicht: (2025)

Disjoint Tours and the Price of Diversity
von: de Berg, Mark, et al.
Veröffentlicht: (2025)

Two Complexity Results on Spanning-Tree Congestion Problems
von: Atalig, Sunny, et al.
Veröffentlicht: (2026)

Revisiting Directed Disjoint Paths on tournaments (and relatives)
von: Gomes, Guilherme C. M., et al.
Veröffentlicht: (2025)

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

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
von: Pilipczuk, Michał, et al.
Veröffentlicht: (2025)

Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
von: Ferdous, S M, et al.
Veröffentlicht: (2023)

Planar Length-Constrained Minimum Spanning Trees
von: Hershkowitz, D Ellis, et al.
Veröffentlicht: (2025)

Spanning and Metric Tree Covers Parameterized by Treewidth
von: Elkin, Michael, et al.
Veröffentlicht: (2025)

Budget and Profit Approximations for Spanning Tree Interdiction
von: Ostrovsky, Rafail, et al.
Veröffentlicht: (2025)

Simple Length-Constrained Minimum Spanning Trees
von: Hershkowitz, D Ellis, et al.
Veröffentlicht: (2024)

Cycle Cancellation for Submodular Fractional Allocations and Applications
von: Chekuri, Chandra, et al.
Veröffentlicht: (2025)

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
von: Choudhary, Keerti, et al.
Veröffentlicht: (2025)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
von: Chitnis, Rajesh, et al.
Veröffentlicht: (2024)

Covering a Few Submodular Constraints and Applications
von: Bajpai, Tanvi, et al.
Veröffentlicht: (2025)

Stochastic Minimum Spanning Trees with a Single Sample
von: Hoeksma, Ruben, et al.
Veröffentlicht: (2024)

Enumerating All Directed Spanning Trees in Optimal Time
von: Gawrychowski, Paweł, et al.
Veröffentlicht: (2026)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
von: Włodarczyk, Michał
Veröffentlicht: (2024)

Parameterized Algorithms for Spanning Tree Isomorphism by Redundant Set Size
von: Shen, Fangjian, et al.
Veröffentlicht: (2025)