An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs

 0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: Vijay V Vazirani

Ngôn ngữ: eng

Ký hiệu phân loại: 511.5 Graph theory

Thông tin xuất bản: 2020

Mô tả vật lý:

Bộ sưu tập: Metadata

ID: 165377

 Comment: 16 pagesWe prove that a fractional perfect matching in a non-bipartite graph can be written, in polynomial time, as a convex combination of perfect matchings. This extends the Birkhoff-von Neumann Theorem from bipartite to non-bipartite graphs. The algorithm of Birkhoff and von Neumann is greedy
  it starts with the given fractional perfect matching and successively "removes" from it perfect matchings, with appropriate coefficients. This fails in non-bipartite graphs -- removing perfect matchings arbitrarily can lead to a graph that is non-empty but has no perfect matchings. Using odd cuts appropriately saves the day.
Tạo bộ sưu tập với mã QR

THƯ VIỆN - TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP.HCM

ĐT: (028) 36225755 | Email: tt.thuvien@hutech.edu.vn

Copyright @2024 THƯ VIỆN HUTECH