Finding popular branchings in vertex-weighted directed graphs

DOI10.1016/j.tcs.2023.113799OpenAlexW4323275935MaRDI QIDQ2693638

Kei Natsui, Kenjiro Takazawa

Publication date: 24 March 2023

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.113799

zbMATH Keywords

algorithmcombinatorial optimizationpopular matchingmin-cost arborescencepopular branching

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal popular matchings
• Popular edges and dominant matchings
• Popular matchings in the stable marriage problem
• Popular branchings and their dual certificates
• Finding popular branchings in vertex-weighted digraphs
• Popular Matchings
• Popular Matchings in the Marriage and Roommates Problems
• Packing rooted directed cuts in a weighted directed graph
• Quasi-Popular Matchings, Optimality, and Extended Formulations
• Popular Matchings and Limits to Tractability
• Popular Matchings with Two-Sided Preferences and One-Sided Ties
• Weighted popular matchings

This page was built for publication: Finding popular branchings in vertex-weighted directed graphs