Showing 2022Show all
2 papers · 1 filter
cs.DS2022
Breaking the Barrier for Subset Feedback Vertex Set in Chordal Graphs
Tian Bai, Mingyu Xiao
The Subset Feedback Vertex Set problem (SFVS), to delete vertices from a given graph such that any vertex in a vertex subset (called a terminal set) is not in a cycle in the re…
cs.GT2022
Facility Location Games Beyond Single-Peakedness: the Entrance Fee Model
Mengfan Ma, Mingyu Xiao, Tian Bai +1
The facility location game has been studied extensively in mechanism design. In the classical model, each agent's cost is solely determined by her distance to the nearest facility.…