Cover Image

Node-Weighted Multicut in Planar Digraphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chekuri, Chandra, Jain, Rhea
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2024)

Approximation Algorithms for Network Design in Non-Uniform Fault Models
by: Chekuri, Chandra, et al.
Published: (2024)

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

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
by: Chekuri, Chandra, et al.
Published: (2024)

Streaming Algorithms for Network Design
by: Chekuri, Chandra, et al.
Published: (2025)

Colorful Priority $k$-Supplier
by: Chekuri, Chandra, et al.
Published: (2024)

On Sparsest Cut and Conductance in Directed Polymatroidal Networks
by: Chekuri, Chandra, et al.
Published: (2024)

Online Disjoint Spanning Trees and Polymatroid Bases
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

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

Fully Dynamic Strongly Connected Components in Planar Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

Mimicking Networks for Constrained Multicuts in Hypergraphs
by: Cho, Kyungjin, et al.
Published: (2024)

Hedgegraph Polymatroids
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

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

Hypergraph Splitting-Off via Element-Connectivity Preserving Reductions
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
by: Chandrasekaran, Karthekeyan, et al.
Published: (2023)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
by: Das, Debarati, et al.
Published: (2026)

Search-Space Reduction Via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion
by: Jansen, Bart M. P., et al.
Published: (2024)

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, et al.
Published: (2026)

Stochastic Embedding of Digraphs into DAGs
by: Filtser, Arnold
Published: (2025)

Uncrossed Multiflows and Applications to Disjoint Paths
by: Chekuri, Chandra, et al.
Published: (2025)

Exponential Time Approximation for Coloring 3-Colorable Graphs
by: Guruswami, Venkatesan, et al.
Published: (2024)

Approximation Algorithms for Digraph Width Parameters
by: Kintali, Shiva, et al.
Published: (2011)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
by: Focke, Jacob, et al.
Published: (2023)

Fully Dynamic Shortest Paths in Sparse Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
by: Hatzel, Meike, et al.
Published: (2022)

All-Pairs Shortest Paths with Few Weights per Node
by: Abboud, Amir, et al.
Published: (2025)

Cycle Cancellation for Submodular Fractional Allocations and Applications
by: Chekuri, Chandra, et al.
Published: (2025)

Covering a Few Submodular Constraints and Applications
by: Bajpai, Tanvi, 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)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
by: Włodarczyk, Michał
Published: (2024)

Integer and Unsplittable Multiflows in Series-Parallel Digraphs
by: Almoghrabi, Mohammed Majthoub, et al.
Published: (2024)

Node-Weighted Triangles: Faster and Simpler
by: Akmal, Shyan, et al.
Published: (2026)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
by: Georgiadis, Loukas, et al.
Published: (2026)

Upward Book Embeddings of Partitioned Digraphs
by: Da Lozzo, Giordano, et al.
Published: (2026)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
by: D'Angelo, Gianlorenzo, et al.
Published: (2025)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
by: Ashvinkumar, Vikrant, et al.
Published: (2026)

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

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

Towards Transitive-free Digraphs
by: Abhinav, Ankit, et al.
Published: (2025)