Recognizing when a preference system is close to admitting a master list
DOI10.1016/j.tcs.2024.114445OpenAlexW4392203713MaRDI QIDQ6124592
Publication date: 28 March 2024
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2024.114445
approximationparameterized complexitypreference systemmaster listpreference swapvertex/edge deletion
Quantum computation (81P68) Group preferences (91B10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Open systems, reduced dynamics, master equations, decoherence (81S22) Parameterized complexity, tractability and kernelization (68Q27) Lists of open problems (00A27) Quantum gates (81P65) Hasse principle, weak and strong approximation, Brauer-Manin obstruction (14G12)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- The complexity of Kemeny elections
- On the parameterized complexity of multiple-interval graph problems
- The stable marriage problem with master preference lists
- Fixed-parameter algorithms for Kemeny rankings
- Voting schemes for which it can be difficult to tell who won the election
- Solving hard stable matching problems involving groups of similar agents
- A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the Technion
- Multidimensional stable roommates with master list
- Distributed stable matching with similar preference lists
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Popular Matchings in the Marriage and Roommates Problems
- The Stable Roommates Problem with Globally Ranked Pairs
- On the power of unique 2-prover 1-round games
- The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
- Scaling Algorithms for Weighted Matching in General Graphs
- Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Reducibility among Combinatorial Problems
- On the Parameterized Complexity of Approximating Dominating Set
- Algorithmics of Matching Under Preferences
- Parameterized Algorithms
- College Admissions and the Stability of Marriage
This page was built for publication: Recognizing when a preference system is close to admitting a master list