POPULAR SPANNING TREES

DOI10.1142/S0129054113500226zbMATH Open1283.68154MaRDI QIDQ5404516FDOQ5404516

Andreas Darmann

Publication date: 24 March 2014

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

spanning treescomputational complexitysocial choice

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Voting schemes for which it can be difficult to tell who won the election
• Sharing a minimal cost spanning tree: beyond the folk solution
• On cost allocation for a spanning tree: A game theoretic approach
• Cost monotonicity, consistency and minimum cost spanning tree games
• Characterizations of the plurality function
• A simplified NP-complete MAXSAT problem
• The Condorcet criterion and committee selection
• Sets of alternatives as Condorcet winners
• An Analysis of Simple Voting Systems for Electing Committees
• On the complexity of achieving proportional representation
• Popular matchings: structure and algorithms
• Optimal popular matchings
• Maximizing the minimum voter satisfaction on spanning trees
• A note on maximizing the minimum voter satisfaction on spanning trees
• Popular mixed matchings

Cited In (6)

• Popular branchings and their dual certificates
• Popular Branchings and Their Dual Certificates
• It is difficult to tell if there is a Condorcet spanning tree
• On weakly and strongly popular rankings
• Popular matchings with weighted voters
• Computational complexity of \(k\)-stable matchings

This page was built for publication: POPULAR SPANNING TREES

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