Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs
From MaRDI portal
Publication:2067633
DOI10.1016/j.tcs.2021.12.009OpenAlexW2926129805MaRDI QIDQ2067633
Publication date: 18 January 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.02425
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of monotone dualization and generating minimal hypergraph transversals
- On the complexity of a restricted list-coloring problem
- Complexity of list coloring problems with a fixed total number of colors
- Restricted coloring models for timetabling
- Generalized coloring for tree-like graphs
- Coloring mixed hypergraphs: theory, algorithms and applications
- Monotone Boolean dualization is in co-NP\([\log^{2}n\).]
- The hardness of 3-uniform hypergraph coloring
- Complexity of identification and dualization of positive Boolean functions
- An expected polynomial time algorithm for coloring 2-colorable 3-graphs
- Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
- New results on monotone dualization and generating hypergraph transversals
- Properly 2-Colouring Linear Hypergraphs
- A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- NP-completeness: A retrospective
- Achieving new upper bounds for the hypergraph duality problem through logic
- Coloring bipartite hypergraphs
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Approximate Hypergraph Coloring under Low-discrepancy and Related Promises
- Advances in Artificial Intelligence
- Foundations of Information and Knowledge Systems
This page was built for publication: Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs
