Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs
type: Item
instance of: scholarly article
title: Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs
published in: Theoretical Computer Science
publication date: 2022-01-18T00:00:00Z
full work available at URL: https://arxiv.org/abs/1904.02425
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7458785
zbMATH Keywords: hypergraph coloring
zbMATH Keywords: hypergraph dualization
zbMATH Keywords: exact algorithms
zbMATH Keywords: quasi-polynomial algorithm
zbMATH Keywords: list coloring
author: Khaled Elbassioni
MaRDI profile type: Publication
OpenAlex ID: W2926129805
cites work: Q4828988
cites work: The hardness of 3-uniform hypergraph coloring
cites work: Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
cites work: Coloring mixed hypergraphs: theory, algorithms and applications
cites work: Q3129926
cites work: Coloring bipartite hypergraphs
cites work: Approximating coloring and maximum independent sets in 3-uniform hypergraphs
cites work: Q3922703
cites work: Q4135588
cites work: Approximate Hypergraph Coloring under Low-discrepancy and Related Promises
cites work: Properly 2-Colouring Linear Hypergraphs
cites work: An expected polynomial time algorithm for coloring 2-colorable 3-graphs
cites work: On the complexity of a restricted list-coloring problem
cites work: Complexity of list coloring problems with a fixed total number of colors
cites work: Generalized coloring for tree-like graphs
cites work: Restricted coloring models for timetabling
cites work: Identifying the Minimal Transversals of a Hypergraph and Related Problems
cites work: NP-completeness: A retrospective
cites work: Complexity of identification and dualization of positive Boolean functions
cites work: A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
cites work: On the complexity of monotone dualization and generating minimal hypergraph transversals
cites work: New results on monotone dualization and generating hypergraph transversals
cites work: New Results on Monotone Dualization and Generating Hypergraph Transversals
cites work: On the Complexity of Dualization of Monotone Disjunctive Normal Forms
cites work: Foundations of Information and Knowledge Systems
cites work: Advances in Artificial Intelligence
cites work: Achieving new upper bounds for the hypergraph duality problem through logic
cites work: Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
DOI: 10.1016/J.TCS.2021.12.009
Recommended article: Exact Algorithms for List-Coloring of Intersecting Hypergraphs.
Recommended article: Near-optimal list colorings
Recommended article: Hypergraph extension of the Alon-Tarsi list coloring theorem
Recommended article: Algorithmic aspects of partial list colourings
Recommended article: Efficiently list‐edge coloring multigraphs asymptotically optimally
Recommended article: Efficiently list-edge coloring multigraphs asymptotically optimally
Recommended article: Efficient algorithms for counting parameterized list \(H\)-colorings
Recommended article: Q5315865
Recommended article: An Exact Algorithm for the Generalized List $T$-Coloring Problem
Recommended article: Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
description: scientific article; zbMATH DE number 7458785