Cover Image

Binary weights spanning trees and the $k$-red spanning tree problem in linear time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Hochbaum, Dorit S.
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Forcing a unique minimum spanning tree and a unique shortest path
by: Gima, Tatsuya, et al.
Published: (2025)

Interdiction of minimum spanning trees and other matroid bases
by: Weninger, Noah, et al.
Published: (2024)

Using random spanning trees in survivable networks design
by: Wrobel, Blazej, et al.
Published: (2025)

Generating pivot Gray codes for spanning trees of complete graphs in constant amortized time
by: Liu, Bowie, et al.
Published: (2025)

Low-degree spanning trees of $2$-edge-connected graphs in linear time
by: Dereniowski, Dariusz, et al.
Published: (2024)

On the complexity of finding a spanning even tree in a graph
by: Hanaka, Tesshu, et al.
Published: (2024)

Fast and Optimal Incremental Parametric Procedure for the Densest Subgraph Problem: An Experimental Study
by: Hochbaum, Dorit S., 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)

Minimal spanning arborescence
by: Ray, Gourab, et al.
Published: (2024)

The problem of computing a $2$-T-connected spanning subgraph with minimum number of edges in directed graphs
by: Jaberi, Raed, et al.
Published: (2024)

Depth first representations of $k^2$-trees
by: Carmona, Gabriel, et al.
Published: (2025)

Grandchildren-weight-balanced binary search trees
by: Jugé, Vincent
Published: (2024)

Generation of weighted trees, block trees and block graphs
by: Ekim, Tınaz, et al.
Published: (2024)

Identifying bubble-like subgraphs in linear-time via a unified SPQR-tree framework
by: Sena, Francisco, et al.
Published: (2026)

Eulerian-spanning set and coboundary operator: An investigation of maxcut beyond planar graphs
by: Fang, Qiming, et al.
Published: (2026)

Computing largest minimum color-spanning intervals of imprecise points
by: Acharyya, Ankush, et al.
Published: (2024)

A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree
by: Elkin, Yury, et al.
Published: (2021)

Minimum projective linearizations of trees in linear time
by: Alemany-Puig, Lluís, et al.
Published: (2021)

Polynomial-time derivation of optimal k-tree topology from Markov networks
by: Dastjerdi, Fereshteh R., et al.
Published: (2024)

Theoretical insights and an experimental comparison of tango trees and multi-splay trees
by: Al-Adhami, Khaleel, et al.
Published: (2024)

Realizing temporal transportation trees
by: Mertzios, George B., et al.
Published: (2024)

Nested and outlier embeddings into trees
by: Chawla, Shuchi, et al.
Published: (2026)

Performance bounds for nearest neighbor search with k-d trees
by: Bazzani, Marco, et al.
Published: (2026)

Constant-time edge label and leaf pointer maintenance on sliding suffix trees
by: Leonard, Laurentius, et al.
Published: (2023)

Terminal Steiner tree problem : Complexity and Algorithms
by: S, Jyothish, et al.
Published: (2026)

Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules
by: He, Xi, et al.
Published: (2025)

Fast decremental tree sums in forests
by: Berendsohn, Benjamin Aram, et al.
Published: (2026)

Binary $k$-Center with Missing Entries: Structure Leads to Tractability
by: Soheil, Farehe, et al.
Published: (2025)

Efficient top-down updates in AVL trees
by: Jugé, Vincent
Published: (2024)

Optimal bounds on a tree inference algorithm
by: Gardiner, Jack, et al.
Published: (2024)

Median and Small Parsimony Problems on RNA trees
by: Marchand, Bertrand, et al.
Published: (2024)

Spanning tree congestion of proper interval graphs
by: Otachi, Yota
Published: (2026)

A near-linear time approximation scheme for $(k,\ell)$-median clustering under discrete Fréchet distance
by: Driemel, Anne, et al.
Published: (2025)

Composing dynamic programming tree-decomposition-based algorithms
by: Baste, Julien
Published: (2019)

Parallel batch queries on dynamic trees: algorithms and experiments
by: Ikram, Humza, et al.
Published: (2025)

A computational study of Gomory-Hu construction tree algorithms
by: Kolmogorov, Vladimir
Published: (2022)

Kd-tree Based Wasserstein Distance Approximation for High-Dimensional Data
by: Teshigawara, Kanata, et al.
Published: (2026)

OrderedCuts: A new approach for computing Gomory-Hu tree
by: Kolmogorov, Vladimir
Published: (2022)

Randomized $k$-server in polynomial time
by: Coester, Christian, et al.
Published: (2026)

Heights of butterfly trees
by: Peca-Medlin, John, et al.
Published: (2025)