Weighted fractional and integral \(k\)-matching in hypergraphs

DOI10.1016/0166-218X(94)00107-OzbMath0823.90131MaRDI QIDQ1346702

Anand Srivastav, Peter Stangier

Publication date: 10 April 1995

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

zbMATH Keywords

randomized algorithmderandomizationstrongly NP-hardweighted hypergraphmaximum \(K\)-matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Linear programming (90C05) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the fractional matching polytope of a hypergraph
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Maximum degree and fractional matchings in uniform hypergraphs
• Geometric algorithms and combinatorial optimization
• On the ratio of optimal integral and fractional covers
• The probabilistic method yields deterministic parallel algorithms
• An algorithmic approach to the Lovász local lemma. I
• A parallel algorithmic version of the local lemma
• Simulating (log ^c n )-wise independence in NC
• On a combinatorial game

This page was built for publication: Weighted fractional and integral \(k\)-matching in hypergraphs