Popular Branchings and Their Dual Certificates

DOI10.1007/978-3-030-45771-6_18zbMath1503.90149arXiv1912.01854OpenAlexW3016662321MaRDI QIDQ5041748

Ulrike Schmidt-Kraepelin, Jannik Matuschke, Tamás Király, Telikepalli Kavitha, Ildikó Schlotter

Publication date: 14 October 2022

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1912.01854

zbMATH Keywords

combinatorial algorithmpopular branchings

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (2)

Popular critical matchings in the many-to-many setting ⋮ Unveiling the truth in liquid democracy with misinformed voters

Cites Work

• Unnamed Item
• It is difficult to tell if there is a Condorcet spanning tree
• Popular mixed matchings
• Popular edges and dominant matchings
• Popular matchings in the stable marriage problem
• Popular branchings and their dual certificates
• The fluid mechanics of liquid democracy
• The convergence of iterative delegations in liquid democracy in a social network
• Finding socially best spanning treesî
• Integer Programming
• Popular Matchings
• Popular Matchings in the Marriage and Roommates Problems
• Popularity, Mixed Matchings, and Self-duality
• Popular Half-Integral Matchings.
• Packing rooted directed cuts in a weighted directed graph
• Popular Matching in Roommates Setting Is NP-hard
• Quasi-popular Matchings, Optimality, and Extended Formulations
• Popular Matchings and Limits to Tractability
• Popular Matchings with Two-Sided Preferences and One-Sided Ties
• POPULAR SPANNING TREES
• A Size-Popularity Tradeoff in the Stable Marriage Problem
• The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences
• Optimum branchings
• Combinatorial optimization. Theory and algorithms.
• College Admissions and the Stability of Marriage

This page was built for publication: Popular Branchings and Their Dual Certificates