Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs

DOI10.1007/978-3-642-04128-0_13MaRDI QIDQ3639242zbMATH OpenOpenAlexFDO

Authors Kazuhisa Makino, Imran Rauf, Khaled Elbassioni

Publication date 29 October 2009

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

Full work available at URL http://edoc.mpg.de/518247

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
• Near-linear approximation algorithms for geometric hitting sets
• Near-linear approximation algorithms for geometric hitting sets
• Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry
• Finding transversals for sets of simple geometric figures

Cited in

(7)

• A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
• Minimal dominating sets in interval graphs and trees
• scientific article; zbMATH DE number 1383707 (Why is no real title available?)
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• Proximity Search for Maximal Subgraph Enumeration
• Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
• Enumerating minimal dominating sets in chordal bipartite graphs

This page was built for publication: Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs

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