Cover Image

Efficient Approximation of Fractional Hypertree Width

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Korchemna, Viktoriia, Lokshtanov, Daniel, Saurabh, Saket, Surianarayanan, Vaishali, Xue, Jie
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Databases Discrete Mathematics G.2.2; G.2.0; F.2.0; F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Approximation Algorithms for Capacitated Vehicle Routing Problems: A Comprehensive Survey
by: Chen, Yongyu
Published: (2023)

An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands
by: Shalaby, Ahmed, et al.
Published: (2024)

An O(log n)-Approximation Algorithm for (p,q)-Flexible Graph Connectivity via Independent Rounding
by: Ibrahimpur, Sharat, et al.
Published: (2025)

Min cost flow on unit capacity networks and convex cost K-flow are as easy as the assignment problem with All-Min-Cuts algorithm
by: Hochbaum, Dorit S.
Published: (2016)

Deterministic Minimum Steiner Cut in Maximum Flow Time
by: Ding, Matthew, et al.
Published: (2023)

Highly Connected Steiner Subgraph -- Parameterized Algorithms and Applications to Hitting Set Problems
by: Eiben, Eduard, et al.
Published: (2023)

Forward-backward Contention Resolution Schemes for Fair Rationing
by: Ma, Will, et al.
Published: (2025)

A polynomial-time algorithm for recognizing high-bandwidth graphs
by: Varona, Luis M. B.
Published: (2026)

Online Bipartite Matching in the Probe-Commit Model
by: Borodin, Allan, et al.
Published: (2023)

Online Matching and Contention Resolution for Edge Arrivals with Vanishing Probabilities
by: Ma, Will, et al.
Published: (2024)

On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
by: MacRury, Calum, et al.
Published: (2022)

Approximation Algorithms for Correlated Knapsack Orienteering
by: Espinosa, David Aleman, et al.
Published: (2024)

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
by: Fairbairn, David L., et al.
Published: (2024)

Better Approximation for Weighted $k$-Matroid Intersection
by: Singer, Neta, et al.
Published: (2024)

Cluster deletion and clique partitioning in graphs with bounded clique number
by: Galesi, Nicola, et al.
Published: (2025)

Loop unrolling of UCA models: distance labeling
by: Soulignac, Francisco J, et al.
Published: (2022)

Efficient Uniform Sampling of Surjections via their Profiles
by: Carayol, Arnaud, et al.
Published: (2026)

Faster Mixing for Triangulations via Transport Flows
by: Alev, Vedat Levi, et al.
Published: (2026)

Polymer Dynamics via Cliques: New Conditions for Approximations
by: Friedrich, Tobias, et al.
Published: (2020)

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

Approximation Algorithms for Action-Reward Query-Commit Matching
by: Derakhshan, Mahsa, et al.
Published: (2026)

Solving Modular Linear Systems with a Constraint by parallel decomposition of the Smith form and extended Euclidean division modulo powers of primes divisors
by: Sule, Virendra
Published: (2025)

Weisfeiler-Leman on graphs of small twin-width
by: Heinrich, Irene, et al.
Published: (2026)

Directed Capacity-Preserving Subgraphs: Hardness and Exact Polynomial Algorithms
by: Chimani, Markus, et al.
Published: (2023)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
by: Lokshtanov, Daniel, et al.
Published: (2024)

Searching in trees with monotonic query times
by: Dereniowski, Dariusz, et al.
Published: (2024)

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

Improving the Crossing Lemma by Characterizing Dense 2-Planar and 3-Planar Graphs
by: Büngener, Aaron, et al.
Published: (2024)

JFR: An Efficient Jump Frontier Relaxation Strategy for Bellman-Ford
by: Wang, Xin, et al.
Published: (2025)

Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
by: Chauhan, Archit, et al.
Published: (2026)

Convergence analysis of t-SNE as a gradient flow for point cloud on a manifold
by: Jeong, Seonghyeon, et al.
Published: (2024)

Reducing Matroid Optimization to Basis Search
by: Streit, Robert, et al.
Published: (2024)

Faster algorithms on linear delta-matroids
by: Koana, Tomohiro, et al.
Published: (2024)

A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees
by: Jacob, Ashwin, et al.
Published: (2026)

New Results on Edge-coloring and Total-coloring of Split Graphs
by: Couto, Fernanda, et al.
Published: (2023)

Beyond Worst-Case Subset Sum: An Adaptive, Structure-Aware Solver with Sub-$2^{n/2}$ Enumeration
by: Salas, Jesus
Published: (2025)

Enumeration of Bases in Matroid with Exponentially Large Ground Set
by: Nishimura, Yuki, et al.
Published: (2025)

Partial Implementation of Max Flow and Min Cost Flow in Almost-Linear Time
by: Kavi, Nithin
Published: (2024)

On the Parameterized Tractability of Packing Vertex-Disjoint A-Paths with Length Constraints
by: Bandopadhyay, Susobhan, et al.
Published: (2026)

Searching in trees with $k$-up-modular cost functions
by: Szyfelbein, Michał
Published: (2025)