Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
From MaRDI portal
Publication:6566595
DOI10.46298/THEORETICS.23.9MaRDI QIDQ6566595
Pankaj Kumar, Sepehr Assadi, [[Person:6083480|Author name not available (Why is that?)]]
Publication date: 3 July 2024
Published in: TheoretiCS (Search for Journal in Brave)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Streaming algorithms for independent sets in sparse hypergraphs
- Graphs with chromatic number close to maximum degree
- Colouring graphs when the number of colours is almost the maximum degree
- An NC algorithm for Brooks' theorem
- Colorings and orientations of graphs
- Three short proofs in graph theory
- On an upper bound of the graph's chromatic number, depending on the graph's degree and density
- A strengthening of Brooks' theorem
- A bound on the strong chromatic index of a graph
- Complexity measures and decision tree complexity: a survey.
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- Concentration of measure and isoperimetric inequalities in product spaces
- Dual lower bounds for approximate degree and Markov-Bernstein inequalities
- A different short proof of Brooks' theorem
- On graph problems in a semi-streaming model
- Brook's theorem
- Streaming and Communication Complexity of Clique Approximation
- Brooks Coloring in Parallel
- Δ-List Vertex Coloring in Linear Time
- Brooks' Theorem and Beyond
- Two applications of information complexity
- Graph Distances in the Data-Stream Model
- A fast parallel algorithm to color a graph with Δ colors
- Communication Steps for Parallel Query Processing
- (Delta+1) Coloring in the Congested Clique Model
- Smaller Cuts, Higher Lower Bounds
- Improved Distributed Delta-Coloring
- Streaming Algorithms for 2-Coloring Uniform Hypergraphs
- An optimal distributed (Δ+1)-coloring algorithm?
- Sublinear Algorithms for (Δ + 1) Vertex Coloring
- Distributed (∆+1)-coloring in sublogarithmic rounds
- A lower bound for the distributed Lovász local lemma
- New proof of brooks' theorem
- Simple, Deterministic, Constant-Round Coloring in the Congested Clique
- Concentration of Measure for the Analysis of Randomized Algorithms
- Graph colouring and the probabilistic method
- Efficient randomized distributed coloring in CONGEST
- Brooks’ theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring
- Deterministic graph coloring in the streaming model
- Near-optimal distributed degree+1 coloring
- Distributed ∆-coloring plays hide-and-seek
- Improved Deterministic (Δ+1) Coloring in Low-Space MPC
- Fast distributed Brooks' theorem
This page was built for publication: Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6566595)
