Cover Image

The Gap Between Greedy Algorithm and Minimum Multiplicative Spanner

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Chen, Yeyuan
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Discrete Mathematics Combinatorics 05
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Light Edge Fault Tolerant Graph Spanners
by: Bodwin, Greg, et al.
Published: (2025)

An Alternate Proof of Near-Optimal Light Spanners
by: Bodwin, Greg
Published: (2023)

Constructive Characterization and Recognition Algorithm for Grafts with a Connected Minimum Join
by: Kita, Nanano
Published: (2025)

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
by: Shakeri, Heman, et al.
Published: (2025)

Greedy Gray Codes for some Restricted Classes of Binary Words
by: Hassler, Nathanaël, et al.
Published: (2024)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
by: Dudeja, Aditi, et al.
Published: (2024)

A Uniformly Random Solution to Algorithmic Redistricting
by: Cai, Jin-Yi, et al.
Published: (2024)

Stable Approximation Algorithms for Dominating Set and Independent Set
by: de Berg, Mark, et al.
Published: (2024)

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
by: Iwata, Satoru, et al.
Published: (2024)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
by: Bourneuf, Romain, et al.
Published: (2025)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
by: Bourneuf, Romain, et al.
Published: (2025)

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

A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
by: Jana, Satyabrata, et al.
Published: (2025)

Greedy Algorithms for Shortcut Sets and Hopsets
by: Bals, Ben, et al.
Published: (2025)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
by: Ghanbari, Babak, et al.
Published: (2026)

Toward Minimum Graphic Parity Networks
by: Cao, Yixin, et al.
Published: (2025)

Locally seeded embeddings, and Ramsey numbers of bipartite graphs with sublinear bandwidth
by: Altschuler, Dylan J., et al.
Published: (2024)

Edge coloring of products of signed graphs
by: Janczewski, Robert, et al.
Published: (2023)

Paths and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances
by: Chen, Yu, et al.
Published: (2024)

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families
by: Chen, Yu, et al.
Published: (2023)

How to Reduce Temporal Cliques to Find Sparse Spanners
by: Angrick, Sebastian, et al.
Published: (2024)

Average-Case Matrix Discrepancy: Asymptotics and Online Algorithms
by: Kunisky, Dmitriy, et al.
Published: (2023)

Greediness is not always a vice: Efficient Discovery Algorithms for Assignment Problems
by: Duvignau, Romaric, et al.
Published: (2024)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
by: Wang, Chen, et al.
Published: (2024)

Minimum Sum Set Cover: Structures and Algorithm
by: Zhang, Zhongyi, et al.
Published: (2026)

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
by: Bencs, Ferenc, et al.
Published: (2024)

Approximating maximum-size properly colored forests
by: Bai, Yuhang, et al.
Published: (2024)

Problems on Group-labeled Matroid Bases
by: Hörsch, Florian, et al.
Published: (2024)

$α_i$-Metric Graphs: Hyperbolicity
by: Dragan, Feodor F., et al.
Published: (2024)

Rainbow Arborescence Conjecture
by: Bérczi, Kristóf, et al.
Published: (2024)

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
by: Holtgrefe, Niels, et al.
Published: (2024)

Cuts in Graphs with Matroid Constraints
by: Banik, Aritra, et al.
Published: (2024)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Deterministic approximation for the volume of the truncated fractional matching polytope
by: Guo, Heng, et al.
Published: (2024)

Clique-free t-matchings in degree-bounded graphs
by: Paluch, Katarzyna, et al.
Published: (2024)

A logarithmic approximation of linearly ordered colourings
by: Håstad, Johan, et al.
Published: (2024)

On the sizes of BDDs and ZDDs representing matroids
by: Emoto, Hiromi, et al.
Published: (2024)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
by: Korhonen, Tuukka, et al.
Published: (2024)

On the number of $k$-mers admitting a given lexicographical minimizer
by: Ingels, Florian, et al.
Published: (2024)

Generalising the maximum independent set algorithm via Boolean networks
by: Gadouleau, Maximilien, et al.
Published: (2024)