Cover Image

Directed Capacity-Preserving Subgraphs: Hardness and Exact Polynomial Algorithms

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chimani, Markus, Ilsen, Max
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Discrete Mathematics 05C21 (Primary) 68R10, 05C20 (Secondary) G.2.2; F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
by: Chimani, Markus, et al.
Published: (2021)

Traffic-Oblivious Multi-Commodity Flow Network Design
by: Chimani, Markus, et al.
Published: (2025)

Designing Capacitated Subnetworks for Shortest Path Routing
by: Chimani, Markus, et al.
Published: (2026)

Exact Minimum Weight Spanners via Column Generation
by: Bökler, Fritz, et al.
Published: (2024)

Simple Approximations for General Spanner Problems
by: Bökler, Fritz, et al.
Published: (2025)

Low Recourse Arborescence Forests Under Uniformly Random Arcs
by: Dahlmeier, J Niklas, et al.
Published: (2025)

No Traffic to Cry: Traffic-Oblivious Link Deactivation for Green Traffic Engineering
by: Ilsen, Max, et al.
Published: (2026)

Exact Algorithms for MaxCut on Split Graphs
by: Lalovic, Marko
Published: (2024)

Bicriteria Submodular Maximization
by: Feldman, Moran, et al.
Published: (2025)

Counting Kernels in Directed Graphs with Arbitrary Orientations
by: Jartoux, Bruno
Published: (2022)

Independent Set Enumeration in King Graphs by Tensor Network Contractions
by: Liang, Kai
Published: (2025)

Completely independent spanning trees in the hypercube
by: Shaw, Benedict Randall
Published: (2024)

Killing a Vortex
by: Thilikos, Dimitrios M., et al.
Published: (2022)

Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
by: Buchbinder, Niv, et al.
Published: (2024)

Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
by: Buchbinder, Niv, et al.
Published: (2024)

Exploration of $k$-edge-deficient temporal graphs in linear time
by: Lahtin, Ivan, et al.
Published: (2026)

Temporalizing digraphs via linear-size balanced bi-trees
by: Bessy, Stéphane, et al.
Published: (2023)

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
by: Rockel-Wolff, Benjamin
Published: (2024)

Tree-independence number VI. Thetas and pyramids
by: Chudnovsky, Maria, et al.
Published: (2025)

Optimized Degree Realization: Minimum Dominating Set & Maximum Matching
by: Bar-Noy, Amotz, et al.
Published: (2025)

Optimal Bounds for the k-Disjoint Paths Problem
by: Cavallaro, Dario, et al.
Published: (2026)

How Local Separators Shape Community Structure in Large Networks
by: Frenkel, Sarah, et al.
Published: (2025)

An Explicit and Efficient $O(n^2)$-Time Algorithm for Sorting Sumsets
by: Mundhra, S.
Published: (2025)

Lower Bounds for the Pfaffian Number of Graphs
by: Junchaya, Enrique, et al.
Published: (2026)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
by: Morse, Gregory, et al.
Published: (2026)

A Systematic Approach to Crossing Numbers of Cartesian Products with Paths
by: Asiri, Zayed, et al.
Published: (2024)

Monotone Arc Diagrams with few Biarcs
by: Chaplick, Steven, et al.
Published: (2024)

Dynamic Traffic Assignment for Public Transport with Vehicle Capacities
by: Patzner, Julian, et al.
Published: (2024)

Sparse Induced Subgraphs of Large Treewidth
by: Bonnet, Édouard
Published: (2024)

A note on the structure of locally finite planar quasi-transitive graphs
by: Giocanti, Ugo
Published: (2024)

Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs
by: Gabryelski, Wojciech, et al.
Published: (2026)

Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
by: Komusiewicz, Christian, et al.
Published: (2023)

Solving the Graph Burning Problem for Large Graphs
by: Pereira, Felipe de Carvalho, et al.
Published: (2024)

Shortest two disjoint paths in conservative graphs
by: Schlotter, Ildikó
Published: (2023)

An algorithmic Vizing's theorem: toward efficient edge-coloring sampling with an optimal number of colors
by: De Meyer, Lucas, et al.
Published: (2025)

Adjacency Labeling Schemes for Small Classes
by: Bonnet, Édouard, et al.
Published: (2024)

Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars
by: Choi, Mujin, et al.
Published: (2025)

Crossing Numbers of Beyond Planar Graphs Re-revisited: A Framework Approach
by: Chimani, Markus, et al.
Published: (2024)

Polynomial Bounds for the Graph Minor Structure Theorem
by: Gorsky, Maximilian, et al.
Published: (2025)

Approximating Graphic Multi-Path TSP and Graphic Ordered TSP
by: Alimi, Morteza, et al.
Published: (2025)