Independent sets versus perfect matchings

DOI10.1016/0304-3975(94)00289-UMaRDI QIDQ673116zbMATH OpenFDO

Authors Shang-Hua Teng

Publication date 28 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

matchingsindependent sets

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Recommendations

• From matchings to independent sets
• Independent set and matching permutations
• Independent sets, matchings, and occupancy fractions
• Problems on matchings and independent sets of a graph
• Matchings and independent sets of a fixed size in regular graphs
• Independent sets and matchings in subcubic graphs
• Independence and matching number of some graphs
• Graphs with independent perfect matchings
• Independent domination and matchings in graphs
• Lower Bounds for Maximal Matchings and Maximal Independent Sets

Cites work

• scientific article; zbMATH DE number 4062621 (Why is no real title available?)
• A Las Vegas RNC algorithm for maximum matching
• A taxonomy of problems with fast parallel algorithms
• Matching is as easy as matrix inversion
• Parallel Prefix Computation
• The complexity of computing the permanent

Cited in

(10)

• New results relating independence and matchings
• Matchings and independent sets of a fixed size in regular graphs
• Random parallel algorithms for finding exact branchings, perfect matchings, and cycles
• Parallel discrete sampling via continuous walks
• Existence of independent random matching
• Relating dissociation, independence, and matchings
• On asymmetric matching between sets
• From matchings to independent sets
• Independent set and matching permutations
• Constructing a perfect matching is in random NC

This page was built for publication: Independent sets versus perfect matchings

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