Publication:741535
From MaRDI portal
Publication:741535
{{DISPLAYTITLE:Hitting sets online and unique-MAX coloring
DOI10.1016/j.dam.2014.06.019zbMath1300.05299arXiv1207.2598OpenAlexW2053576536MaRDI QIDQ741535
Publication date: 12 September 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1207.2598
Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Transversal (matching) theory (05D15) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)
Related Items
Tight bounds for online weighted tree augmentation, Hitting geometric objects online via points in \(\mathbb{Z}^d\), Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\), On the diameter of tree associahedra, Tight Bounds for Online Weighted Tree Augmentation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for geometric set cover
- Hitting sets when the VC-dimension is small
- Computational models and task scheduling for parallel sparse Cholesky factorization
- Optimal node ranking of trees
- On a graph partition problem with application to VLSI layout
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- On neighbors in geometric permutations.
- Optimal node ranking of tree in linear time
- Ordered colourings
- Almost optimal set covers in finite VC-dimension
- Covering rectilinear polygons with axis-parallel rectangles
- A threshold of ln n for approximating set cover
- The Online Set Cover Problem
- Approximation schemes for covering and packing problems in image processing and VLSI
- A Greedy Heuristic for the Set-Covering Problem
- Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
- Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles
