Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs

DOI10.1016/J.TCS.2021.12.009MaRDI QIDQ2067633zbMATH OpenOpenAlexFDO

Authors Khaled Elbassioni

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

zbMATH Keywords

exact algorithmshypergraph coloringhypergraph dualizationlist coloringquasi-polynomial algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Exact algorithms for list-coloring of intersecting hypergraphs
• Near-optimal list colorings
• Hypergraph extension of the Alon-Tarsi list coloring theorem
• Algorithmic aspects of partial list colourings
• Efficiently list‐edge coloring multigraphs asymptotically optimally
• Efficiently list-edge coloring multigraphs asymptotically optimally
• Efficient algorithms for counting parameterized list H-colorings
• scientific article; zbMATH DE number 2204176
• An exact algorithm for the generalized list T-coloring problem
• Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors

Cites work

• A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
• Achieving new upper bounds for the hypergraph duality problem through logic
• Advances in Artificial Intelligence
• An expected polynomial time algorithm for coloring 2-colorable 3-graphs
• Approximate hypergraph coloring under low-discrepancy and related promises
• Approximating coloring and maximum independent sets in 3-uniform hypergraphs
• Coloring bipartite hypergraphs
• Coloring mixed hypergraphs: theory, algorithms and applications
• Complexity of identification and dualization of positive Boolean functions
• Complexity of list coloring problems with a fixed total number of colors
• Foundations of Information and Knowledge Systems
• Generalized coloring for tree-like graphs
• scientific article; zbMATH DE number 1002208 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 2119715 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
• New results on monotone dualization and generating hypergraph transversals
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• NP-completeness: a retrospective
• On the complexity of a restricted list-coloring problem
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the complexity of monotone dualization and generating minimal hypergraph transversals
• Properly 2-Colouring Linear Hypergraphs
• Restricted coloring models for timetabling
• The hardness of 3-uniform hypergraph coloring

This page was built for publication: Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2067633)