Popular branchings and their dual certificates

DOI10.1007/S10107-021-01659-6MaRDI QIDQ2118146zbMATH OpenOpenAlexFDO

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

Publication date 22 March 2022

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10107-021-01659-6

zbMATH Keywords

branching problemcombinatorial algorithm

Mathematics Subject Classification ID

General topics in the theory of algorithms (68W01) Combinatorial optimization (90C27) Optimality conditions and duality in mathematical programming (90C46)

Recommendations

• Popular branchings and their dual certificates
• Popular Matchings: Structure and Algorithms
• Popular matchings: structure and algorithms
• Popular ranking
• Popular matchings

Cites work

• A Size-Popularity Tradeoff in the Stable Marriage Problem
• Binary voting with delegable proxy: an analysis of liquid democracy
• College Admissions and the Stability of Marriage
• Combinatorial optimization. Theory and algorithms.
• Finding socially best spanning treesî
• Integer Programming
• It is difficult to tell if there is a Condorcet spanning tree
• Optimum branchings
• Packing rooted directed cuts in a weighted directed graph
• Popular Half-Integral Matchings.
• Popular Matchings
• Popular matchings and limits to tractability
• Popular matchings in the marriage and roommates problems
• Popular matchings in the stable marriage problem
• Popular matchings with two-sided preferences and one-sided ties
• Popular mixed matchings
• Popular spanning trees
• Popularity, mixed matchings, and self-duality
• Quasi-popular Matchings, Optimality, and Extended Formulations
• The convergence of iterative delegations in liquid democracy in a social network
• The ellipsoid method and its consequences in combinatorial optimization
• The fluid mechanics of liquid democracy
• The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences

Cited in

(9)

• Finding popular branchings in vertex-weighted digraphs
• An approval-based model for single-step liquid democracy
• Finding popular branchings in vertex-weighted directed graphs
• Popular branchings and their dual certificates
• On weakly and strongly popular rankings
• Popular matchings with weighted voters
• Computational complexity of \(k\)-stable matchings
• Popular arborescences and their matroid generalization
• Combinatorial optimization. Abstracts from the workshop held November 10--15, 2024

This page was built for publication: Popular branchings and their dual certificates

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