Abstrakt. Vi anser att maximal storlek populära matchningsproblem i en rumskamrat exempel G = (V, E) med strikta preferenslistor. En matchande M är populär om det inte finns någon matchande M i G sådan att de hörn som föredrar M till M överträffar dem som föredrar M till M. Vi visar att det är NP-hård att beräkna en maximal storlek populär matchning i G. Detta är i motsats till den dragbarhet av detta problem i bipartite grafer där en maximal storlek populär matchning kan beräknas i linjär tid. Vi definierar en subklass av populära matchningar av maximal storlek som kallas starkt dominanta matchningar och visar en linjär tidsalgoritm för att lösa det starkt dominanta matchningsproblemet i en rumskamrats instans. Vi anser att en generalisering av den max-storlek populära matchning problem i bipartite grafer: detta är den max-vikt populära matchning problem där det finns också en vikt funktion w : E → R och vi söker en populär matchning av största vikt. Vi visar att detta är ett NP-hard problem och detta är så även när w(e)... {1, 2} för varje e E. Vi visar också en algoritm med körtid O * (2 n/4 ) för att hitta en maximal vikt populär matchning i G = (A  till B, E) på n hörn.
En effektiv algoritm gavs också i REF för att beräkna en starkt dominant matchning i en rumskamrat instans.
Max-size popular matchings and extensions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}