Cover Image

Stochastic Embedding of Digraphs into DAGs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Filtser, Arnold
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

Hop-Constrained Metric Embeddings and their Applications
by: Filtser, Arnold
Published: (2021)

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
by: Filtser, Arnold
Published: (2024)

Scattering and Sparse Partitions, and their Applications
by: Filtser, Arnold
Published: (2020)

A face cover perspective to $\ell_1$ embeddings of planar graphs
by: Filtser, Arnold
Published: (2019)

On Strong Diameter Padded Decompositions
by: Filtser, Arnold
Published: (2019)

How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs
by: Conroy, Jonathan, et al.
Published: (2025)

FPT approximations for Capacitated Sum of Radii and Diameters
by: Filtser, Arnold, et al.
Published: (2024)

Highway Dimension: a Metric View
by: Feldmann, Andreas Emil, et al.
Published: (2024)

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
by: Bhore, Sujoy, et al.
Published: (2023)

Dynamic Light Spanners in Doubling Metrics
by: Bhore, Sujoy, et al.
Published: (2026)

Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes
by: Filtser, Arnold, et al.
Published: (2026)

Parallel PLL on DAGs
by: Steil, Patrick
Published: (2025)

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

Covering Approximate Shortest Paths with DAGs
by: Assadi, Sepehr, et al.
Published: (2025)

Testing Monotonicity of Real-Valued Functions on DAGs
by: Yoshida, Yuichi
Published: (2026)

DAG Projections: Reducing Distance and Flow Problems to DAGs
by: Haeupler, Bernhard, et al.
Published: (2026)

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

Node-Weighted Multicut in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2026)

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

DAG Covers: The Steiner Point Effect
by: Bhore, Sujoy, et al.
Published: (2026)

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

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

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

A $\frac{4}{3}$-Approximation for the Maximum Leaf Spanning Arborescence Problem in DAGs
by: Neuwohner, Meike
Published: (2024)

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

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

Subset verification and search algorithms for causal DAGs
by: Choo, Davin, et al.
Published: (2023)

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

Optimal Padded Decomposition For Bounded Treewidth Graphs
by: Filtser, Arnold, et al.
Published: (2024)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
by: Das, Debarati, 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)

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

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

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
by: Foucaud, Florent, et al.
Published: (2026)

Safe Sequences via Dominators in DAGs for Path-Covering Problems
by: Sena, Francisco, et al.
Published: (2024)

Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
by: Chakraborty, Dibyayan, et al.
Published: (2024)

The Squishy Grid Problem
by: Cai, Zixi, et al.
Published: (2025)

Online Monotone Metric Embeddings
by: Coester, Christian, et al.
Published: (2026)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

Scheduling on a Stochastic Number of Machines
by: Buchem, Moritz, et al.
Published: (2024)