Cover Image

Simple Approximations for General Spanner Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bökler, Fritz, Chimani, Markus, Jasper, Henning
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Discrete Mathematics Combinatorics 68R10 (Primary) 05C85, 90C11 (Secondary) F.2.2; G.2.1; G.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Exact Minimum Weight Spanners via Column Generation
by: Bökler, Fritz, et al.
Published: (2024)

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
by: Chimani, Markus, et al.
Published: (2021)

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

Traffic-Oblivious Multi-Commodity Flow Network Design
by: Chimani, Markus, et al.
Published: (2025)

Designing Capacitated Subnetworks for Shortest Path Routing
by: Chimani, Markus, et al.
Published: (2026)

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
by: Rockel-Wolff, Benjamin
Published: (2024)

Exploration of $k$-edge-deficient temporal graphs in linear time
by: Lahtin, Ivan, et al.
Published: (2026)

Solving the Graph Burning Problem for Large Graphs
by: Pereira, Felipe de Carvalho, et al.
Published: (2024)

Killing a Vortex
by: Thilikos, Dimitrios M., et al.
Published: (2022)

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

Low Recourse Arborescence Forests Under Uniformly Random Arcs
by: Dahlmeier, J Niklas, et al.
Published: (2025)

Bicriteria Submodular Maximization
by: Feldman, Moran, et al.
Published: (2025)

How Local Separators Shape Community Structure in Large Networks
by: Frenkel, Sarah, et al.
Published: (2025)

The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
by: Morse, Gregory, et al.
Published: (2026)

Exact Algorithms for MaxCut on Split Graphs
by: Lalovic, Marko
Published: (2024)

Lower Bounds for the Pfaffian Number of Graphs
by: Junchaya, Enrique, et al.
Published: (2026)

Tree-independence number VI. Thetas and pyramids
by: Chudnovsky, Maria, et al.
Published: (2025)

m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

Approximating Graphic Multi-Path TSP and Graphic Ordered TSP
by: Alimi, Morteza, et al.
Published: (2025)

The Bottom-Left Algorithm for the Strip Packing Problem
by: Hougardy, Stefan, et al.
Published: (2024)

Counting Kernels in Directed Graphs with Arbitrary Orientations
by: Jartoux, Bruno
Published: (2022)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
by: Heimann, Sophia, et al.
Published: (2024)

Optimal Bounds for the k-Disjoint Paths Problem
by: Cavallaro, Dario, et al.
Published: (2026)

Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars
by: Choi, Mujin, et al.
Published: (2025)

Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
by: Buchbinder, Niv, et al.
Published: (2024)

Optimal Path Partitions in Subcubic and Almost-subcubic Graphs
by: Masařík, Tomáš, et al.
Published: (2026)

Revisiting Chazelle's Implementation of the Bottom-Left Heuristic: A Corrected and Rigorous Analysis
by: Michel, Stefan
Published: (2025)

On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
by: Laekhanukit, Bundit
Published: (2024)

Independent Set Enumeration in King Graphs by Tensor Network Contractions
by: Liang, Kai
Published: (2025)

Completely independent spanning trees in the hypercube
by: Shaw, Benedict Randall
Published: (2024)

Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing
by: Krishnaswamy, Ravishankar, et al.
Published: (2014)

Golden Ratio Growth and Phase Transitions in Chromatic Counts of Circular Chord Graphs
by: Lopez-Bonilla, Rogelio N., et al.
Published: (2025)

Adjacency Labeling Schemes for Small Classes
by: Bonnet, Édouard, et al.
Published: (2024)

Shortest two disjoint paths in conservative graphs
by: Schlotter, Ildikó
Published: (2023)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

A New Temporal Interpretation of Cluster Editing
by: Bocci, Cristiano, et al.
Published: (2022)

Identification to Subclasses of Chordal Graphs
by: Golovach, Petr A., et al.
Published: (2026)

Polyhedral approach to weighted connected matchings in general graphs
by: Samer, Phillippe, et al.
Published: (2023)

Computing distances is FPT on graph associahedra and W[2]-hard on hypergraphic polytopes
by: Cunha, Luís Felipe I., et al.
Published: (2025)