Independent sets versus perfect matchings

DOI10.1016/0304-3975(94)00289-UzbMATH Open0873.68082MaRDI QIDQ673116FDOQ673116

Authors: Shang-Hua Teng 

Publication date: 28 February 1997

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

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

zbMATH Keywords

matchingsindependent sets

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Cites Work

• The complexity of computing the permanent
• A taxonomy of problems with fast parallel algorithms
• Parallel Prefix Computation
• Matching is as easy as matrix inversion
• A Las Vegas RNC algorithm for maximum matching
• Title not available (Why is that?)

Cited In (10)

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

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)