Popular spanning trees

DOI10.1142/S0129054113500226MaRDI QIDQ5404516zbMATH OpenFDO

Authors 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)

Recommendations

• It is difficult to tell if there is a Condorcet spanning tree
• Finding socially best spanning treesî
• A note on maximizing the minimum voter satisfaction on spanning trees
• Maximizing the minimum voter satisfaction on spanning trees
• Computing with voting trees

Cites work

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

Cited in

(11)

• Popular branchings and their dual certificates
• Finding socially best spanning treesî
• On weakly and strongly popular rankings
• Popular matchings with weighted voters
• Computational complexity of \(k\)-stable matchings
• The traveling group problem
• Popular branchings and their dual certificates
• A note on maximizing the minimum voter satisfaction on spanning trees
• A preference-based approach to spanning trees and shortest paths problems
• It is difficult to tell if there is a Condorcet spanning tree
• Maximizing the minimum voter satisfaction on spanning trees

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)