Generating partial and multiple transversals of a hypergraph

DOI10.1007/3-540-45022-X_50MaRDI QIDQ2754179zbMATH OpenFDO

Authors Endre Boros, Kazuhisa Makino, Vladimir Gurvich, Leonid G. Khachiyan

Publication date 11 November 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-45022-X_50

Mathematics Subject Classification ID

Hypergraphs (05C65) Transversal (matching) theory (05D15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
• Dual-bounded generating problems: Weighted transversals of a hypergraph
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• Computing and Combinatorics
• Resolution based algorithms for the transversal hypergraph generation problem

Cited in

(24)

• Generating hinges from arbitrary subhypergraphs
• An inequality for polymatroid functions and its applications.
• Dual-bounded generating problems: Weighted transversals of a hypergraph
• Resolution based algorithms for the transversal hypergraph generation problem
• On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
• Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
• Transversal hypergraphs and families of polyhedral cones
• A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs
• Incremental complexity of a bi-objective hypergraph transversal problem
• Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
• Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems
• Generating dual-bounded hypergraphs
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• Hypergraph transversal computation and related problems in logic and AI
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Enumerating minimal transversals of hypergraphs without small holes
• A Lower Bound for the HBC Transversal Hypergraph Generation
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals
• On a logical approach to estimating computational complexity of potentially intractable problems.
• Foundations of Information and Knowledge Systems
• Covering-based numbers related to the LS-category of finite spaces
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• On the complexity of monotone dualization and generating minimal hypergraph transversals
• Scientific contributions of Leo Khachiyan (a short overview)

This page was built for publication: Generating partial and multiple transversals of a hypergraph

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