Simple approximation algorithms for MAXNAESP and hypergraph 2-colorability

DOI10.1007/3-540-46632-0_6MaRDI QIDQ4511216zbMATH OpenFDO

Authors Daya Ram Gaur, Ramesh Krishnamurti

Publication date 13 February 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-46632-0_6

zbMATH Keywords

approximation algorithmshypergraph 2-colorabilityset splitting

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Review text

Hypergraph 2-colorability, also known as set splitting, is a widely studied problem in graph theory. The authors recast the maximization version of it as a special type of satisfiability problem and give approximation algorithms for it. For the entire collection see [Zbl 0933.00045].

Recommendations

• Simple approximation algorithms for MAXNAESP and hypergraph 2-colorability
• Approximate coloring of uniform hypergraphs (extended abstract)
• Approximate hypergraph coloring
• Approximating coloring and maximum independent sets in 3-uniform hypergraphs
• scientific article; zbMATH DE number 1002208

Cited in

(1)

• Simple approximation algorithms for MAXNAESP and hypergraph 2-colorability

This page was built for publication: Simple approximation algorithms for MAXNAESP and hypergraph 2-colorability

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