Buchumschlag

Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Dong, Sally, Ye, Guanghao
Format:	Preprint
Veröffentlicht:	2023
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

Optimal Padded Decomposition For Bounded Treewidth Graphs
von: Filtser, Arnold, et al.
Veröffentlicht: (2024)

Faster Weak Expander Decompositions and Approximate Max Flow
von: Fleischmann, Henry, et al.
Veröffentlicht: (2025)

Optimized 2-Approximation of Treewidth
von: Belbasi, Mahdi, et al.
Veröffentlicht: (2024)

Residue Domination in Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2024)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2021)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
von: Abbasi, Ali, et al.
Veröffentlicht: (2026)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
von: Brand, Jan van den, et al.
Veröffentlicht: (2024)

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
von: de Vos, Tijn, et al.
Veröffentlicht: (2024)

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
von: Wlodarczyk, Michal
Veröffentlicht: (2023)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
von: Esmer, Barış Can, et al.
Veröffentlicht: (2024)

Faster MAX-CUT on Bounded Threshold Rank Graphs
von: Anderson, Prashanti, et al.
Veröffentlicht: (2025)

E-Graphs as Circuits, and Optimal Extraction via Treewidth
von: Sun, Glenn, et al.
Veröffentlicht: (2024)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)

Approximate Min-Sum Subset Convolution
von: Stoian, Mihail
Veröffentlicht: (2024)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
von: Łącki, Jakub, et al.
Veröffentlicht: (2025)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
von: Ashvinkumar, Vikrant, et al.
Veröffentlicht: (2024)

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

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
von: Anand, Aditya, et al.
Veröffentlicht: (2025)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
von: Bringmann, Karl, et al.
Veröffentlicht: (2024)

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
von: Chaplick, Steven, et al.
Veröffentlicht: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2025)

Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors
von: Sharma, Roohani, et al.
Veröffentlicht: (2026)

Dynamic Treewidth in Logarithmic Time
von: Korhonen, Tuukka
Veröffentlicht: (2025)

Losing Treewidth In The Presence Of Weights
von: Włodarczyk, Michał
Veröffentlicht: (2024)

FPT Approximations for Fair $k$-Min-Sum-Radii
von: Carta, Lena, et al.
Veröffentlicht: (2024)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
von: Focke, Jacob, et al.
Veröffentlicht: (2022)

Simpler and Faster Directed Low-Diameter Decompositions
von: Li, Jason
Veröffentlicht: (2025)

Faster Algorithms for Fair Max-Min Diversification in $\mathbb{R}^d$
von: Kurkure, Yash, et al.
Veröffentlicht: (2024)

Faster Approximate Linear Matroid Intersection
von: Terao, Tatsuya
Veröffentlicht: (2026)

Improved Bounds for Rectangular Monotone Min-Plus Product and Applications
von: Dürr, Anita
Veröffentlicht: (2022)

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
von: Kociumaka, Tomasz, et al.
Veröffentlicht: (2025)

Sparse Outerstring Graphs Have Logarithmic Treewidth
von: An, Shinwoo, et al.
Veröffentlicht: (2024)

Generalized Graph Packing Problems Parameterized by Treewidth
von: Esmer, Barış Can, et al.
Veröffentlicht: (2025)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
von: Cheng, Yu, et al.
Veröffentlicht: (2024)

Faster Algorithms for Graph Monopolarity
von: Philip, Geevarghese, et al.
Veröffentlicht: (2024)

Faster Algorithms for Schatten-p Low Rank Approximation
von: Kacham, Praneeth, et al.
Veröffentlicht: (2024)

Faster Approximate Fixed Points of $\ell_\infty$-Contractions
von: Feodorov, Andrei, et al.
Veröffentlicht: (2026)

A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover
von: Bhangale, Amey, et al.
Veröffentlicht: (2026)

Visualizing Treewidth
von: Chiu, Alvin, et al.
Veröffentlicht: (2025)

Distributed Treewidth Computation and Courcelle's Theorem in the CONGEST Model
von: Jauregui, Benjamin, et al.
Veröffentlicht: (2018)