Cover Image

Tree Coloring: Random Order and Predictions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Frei, Fabian, Gehnen, Matthias, Komm, Dennis, Královič, Rastislav, Královič, Richard, Rossmanith, Peter, Stocker, Moritz
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

Time-Optimal $k$-Server
by: Frei, Fabian, et al.
Published: (2025)

Online Unbounded Knapsack
by: Böckenhauer, Hans-Joachim, et al.
Published: (2024)

Stealing From the Dragon's Hoard: Online Unbounded Knapsack With Removal
by: Gehnen, Matthias, et al.
Published: (2025)

Forbidden Subgraph Problems with Predictions
by: Böckenhauer, Hans-Joachim, et al.
Published: (2025)

Online Knapsack Problems with Estimates
by: Balabán, Jakub, et al.
Published: (2025)

Removable Online Knapsack and Advice
by: Böckenhauer, Hans-Joachim, et al.
Published: (2020)

Online Bin Packing with Item Size Estimates
by: Gehnen, Matthias, et al.
Published: (2025)

Online General Knapsack with Reservation Costs
by: Burjons, Elisabet, et al.
Published: (2025)

Graph Exploration with Edge Weight Estimates
by: Gehnen, Matthias, et al.
Published: (2025)

Uniform Universal Sets, Splitters, and Bisectors
by: Burjons, Elisabet, et al.
Published: (2025)

Tokenisation over Bounded Alphabets is Hard
by: Kastreva, Violeta, et al.
Published: (2025)

Random-Order Interval Selection
by: Borodin, Allan, et al.
Published: (2024)

Expanderizing Higher Order Random Walks
by: Alev, Vedat Levi, et al.
Published: (2024)

Solving Partial Dominating Set and Related Problems Using Twin-Width
by: Balabán, Jakub, et al.
Published: (2025)

Approximating the Top Eigenvector in Random Order Streams
by: Kacham, Praneeth, et al.
Published: (2024)

Random Order Set Cover is as Easy as Offline
by: Gupta, Anupam, et al.
Published: (2021)

Unit Interval Selection in Random Order Streams
by: Alexandru, Cezar-Mihail, et al.
Published: (2026)

On the Complexity of Distributed Edge Coloring and Orientation Problems
by: Brandt, Sebastian, et al.
Published: (2025)

A Learning Perspective on Random-Order Covering Problems
by: Gupta, Anupam, et al.
Published: (2025)

Weighted Matching in the Random-Order Streaming and Robust Communication Models
by: Hashemi, Diba, et al.
Published: (2024)

Bin Packing under Random-Order: Breaking the Barrier of 3/2
by: Hebbar, Anish, et al.
Published: (2024)

Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
by: Buchbinder, Niv, et al.
Published: (2026)

Hitting Meets Packing: How Hard Can it Be?
by: Focke, Jacob, et al.
Published: (2024)

Parallel Derandomization for Coloring
by: Coy, Sam, et al.
Published: (2023)

Optimal (degree+1)-Coloring in Congested Clique
by: Coy, Sam, et al.
Published: (2023)

Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs
by: Ito, Takehiro, et al.
Published: (2025)

Online Learning in the Random Order Model
by: Bernasconi, Martino, et al.
Published: (2025)

Coloring Reconfiguration under Color Swapping
by: Fuchs, Janosch, et al.
Published: (2025)

Deterministic Edge Coloring with few Colors in CONGEST
by: Blikstad, Joakim, et al.
Published: (2026)

Brief Announcement: Parallel Construction of Bumped Ribbon Retrieval
by: Becht, Matthias, et al.
Published: (2024)

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
by: Kaul, Matthias, et al.
Published: (2025)

Tree Search With Predictions
by: Dinitz, Michael, et al.
Published: (2026)

Coloring 3-Colorable Graphs with Low Threshold Rank
by: Hsieh, Jun-Ting
Published: (2025)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
by: Bansal, Nikhil, et al.
Published: (2026)

Solving Random Planted CSPs below the $n^{k/2}$ Threshold
by: Basu, Arpon, et al.
Published: (2025)

Generalized Assignment and Knapsack Problems in the Random-Order Model
by: Klimm, Max, et al.
Published: (2025)

Improving Order with Queues
by: Karrenbauer, Andreas, et al.
Published: (2022)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
by: Frei, Fabian, et al.
Published: (2024)

Kernelization for $H$-Coloring
by: Berkman, Yael, et al.
Published: (2025)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
by: Frei, Fabian, et al.
Published: (2025)