Buchumschlag

A $\frac{4}{3}$-Approximation for the Maximum Leaf Spanning Arborescence Problem in DAGs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Neuwohner, Meike
Format:	Preprint
Veröffentlicht:	2024
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

Approximation Schemes for Planar Graph Connectivity Problems
von: Neuwohner, Meike, et al.
Veröffentlicht: (2025)

A Better-Than-2 Approximation for the Directed Tree Augmentation Problem
von: Neuwohner, Meike, et al.
Veröffentlicht: (2025)

Covering Approximate Shortest Paths with DAGs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Parameterized Algorithms for the Steiner Arborescence Problem on a Hypercube
von: Mahapatra, Sugyani, et al.
Veröffentlicht: (2021)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)

DAG Projections: Reducing Distance and Flow Problems to DAGs
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
von: Armbruster, Susanne, et al.
Veröffentlicht: (2024)

Low-Cost Arborescence Under Edge Faults
von: Dey, Dipan, et al.
Veröffentlicht: (2026)

Parallel PLL on DAGs
von: Steil, Patrick
Veröffentlicht: (2025)

Stochastic Embedding of Digraphs into DAGs
von: Filtser, Arnold
Veröffentlicht: (2025)

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

Rainbow Arborescence Conjecture
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

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

Testing Monotonicity of Real-Valued Functions on DAGs
von: Yoshida, Yuichi
Veröffentlicht: (2026)

Approximate Spanning Tree Counting from Uncorrelated Edge Sets
von: Liu, Yang P., et al.
Veröffentlicht: (2025)

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

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

FPT Approximations for Connected Maximum Coverage
von: Inamdar, Tanmay, et al.
Veröffentlicht: (2026)

A Simple 2-Approximation for Maximum-Leaf Spanning Tree
von: Liao, I-Cheng, et al.
Veröffentlicht: (2023)

Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences
von: Mihalák, Matúš, et al.
Veröffentlicht: (2015)

A Simple 4-Approximation Algorithm for Maximum Agreement Forests on Multiple Unrooted Binary Trees
von: Dempsey, Jordan, et al.
Veröffentlicht: (2024)

Half-Approximating Maximum Dicut in the Streaming Setting
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Improved Approximation Algorithm for Maximum Balanced Biclique
von: Manurangsi, Pasin
Veröffentlicht: (2026)

Optimal 4-Approximation for the Correlated Pandora's Problem
von: Bansal, Nikhil, et al.
Veröffentlicht: (2025)

Safe Sequences via Dominators in DAGs for Path-Covering Problems
von: Sena, Francisco, et al.
Veröffentlicht: (2024)

Approximating Maximum Matching Requires Almost Quadratic Time
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
von: Norose, Ryoma, et al.
Veröffentlicht: (2024)

3/2-Approximation for the Forest Augmentation Problem
von: Çivril, Ali
Veröffentlicht: (2024)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2026)

Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model
von: Suzuki, Ryo, et al.
Veröffentlicht: (2026)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
von: Zheng, Da Wei, et al.
Veröffentlicht: (2023)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
von: Agarwal, Arpit, et al.
Veröffentlicht: (2024)

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
von: Adil, Deeksha, et al.
Veröffentlicht: (2024)

Subset verification and search algorithms for causal DAGs
von: Choo, Davin, et al.
Veröffentlicht: (2023)

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2025)

Approximation of Spanning Tree Congestion using Hereditary Bisection
von: Kolman, Petr
Veröffentlicht: (2024)

Two New Upper Bounds for the Maximum k-plex Problem
von: Zheng, Jiongzhi, et al.
Veröffentlicht: (2023)

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
von: Großmann, Ernestine, et al.
Veröffentlicht: (2026)

A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
von: Zhou, Yi, et al.
Veröffentlicht: (2025)

4/3-Approximation of Graphic TSP
von: Çivril, Ali
Veröffentlicht: (2023)