On the fractional chromatic number of monotone self-dual Boolean functions

DOI10.1016/j.disc.2008.01.028zbMath1170.05308OpenAlexW1982921028MaRDI QIDQ1011723

Kazuhisa Makino, Daya Ram Gaur

Publication date: 9 April 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.01.028

zbMATH Keywords

fractional chromatic numberhypergraph transversalsmonotone self-dual functionsnon-dominated coteries

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Uses Software

• LPbook

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The availability of crumbling wall quorum systems
• Computational aspects of monotone dualization: a brief survey
• Dualization of regular Boolean functions
• Critical hypergraphs for the weak chromatic number
• An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
• Monotone Boolean dualization is in co-NP\([\log^{2}n\).]
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
• Complexity of identification and dualization of positive Boolean functions
• How to assign votes in a distributed system
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• The Maximum Latency and Identification of Positive Boolean Functions
• NP-completeness: A retrospective
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Dual subimplicants of positive Boolean functions
• Algorithm Theory - SWAT 2004
• LATIN 2004: Theoretical Informatics
• Linear programming. Foundations and extensions

This page was built for publication: On the fractional chromatic number of monotone self-dual Boolean functions