Search

We consider the problem of finding a popular matching in the Weighted Capacitated\ud House Allocation problem (WCHA). An instance of WCHA involves a set of agents\ud and a set of houses. Each agent has a positive weight indicating his priority, and a\ud preference list in which a subset of houses are ranked in strict order. Each house has\ud a capacity that indicates the maximum number of agents who could be matched to\ud it. A matching M of agents to houses is popular if there is no other matching M′\ud such that the total weight of the agents who prefer their allocation in M′\ud to that in\ud M exceeds the total weight of the agents who prefer their allocation in M to that in\ud M′\ud . Here, we give an O(\ud √\ud Cn1 + m) algorithm to determine if an instance of WCHA\ud admits a popular matching, and if so, to find a largest such matching, where C is the\ud total capacity of the houses, n1 is the number of agents, and m is the total length of\ud the agents’ preference lists.

We consider variants of the classical stable marriage problem in which preference lists may contain ties, and may be of bounded length. Such restrictions arise naturally in practical applications, such as centralised matching schemes that assign graduating medical students to their first hospital posts. In such a setting, weak stability is the most common solution concept, and it is known that weakly stable matchings can have different sizes. This motivates the problem of finding a maximum cardinality weakly stable matching, which is known to be NP-hard in general. We show that this problem is solvable in polynomial time if each man's list is of length at most 2 (even for women's lists that are of unbounded length). However if each man's list is of length at most 3, we show that the problem becomes NP-hard (even if each women's list is of length at most 3) and not approximable within some δ>1 (even if each woman's list is of length at most 4).

We study the problem of allocating students to projects, where both students and lecturers have preferences over projects, and both projects and lecturers have capacities. In this context we seek a stable matching of students to projects, which respects these preference and capacity constraints. Here, the stability definition generalises the corresponding notion in the context of the classical Hospitals/Residents problem. We show that stable matchings can have different sizes, which motivates max-spa-p, the problem of finding maximum cardinality stable matching. We prove that max-spa-p is NP-hard and not approximable within δ, for some δ>1, unless P=NP. On the other hand, we give an approximation algorithm with a performance guarantee of 2 for max-spa-p.

Given two graphs G and G2, the Ramsey number R(G ,G2) is the smallest integer N such that for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cn denote the cycle of order n and Pk be the path of order k. The Tadpole Graph Tn,k is the graph created by concatenating Cn and Pk with an edge from any vertex of Cn to a pendant of Pk for integers n = 3 and k = 0. A Shell Graph Sn,n−3 is a cycle graph with (n-3) chords sharing a common end point called the apex. De ined the Marking-Tadpole Graph Mp is a graph derived from Tadpole Graph Tn,k where every vertices are adjacent to every vertices of the graph. Moreover, the Marking-Shell Graph Jp is a graph originated from Shell Graph where every vertices are adjacent to every vertices of the graph as well. In this study, we show the combinatorial relationships and identities of R(Mp,C4) to R(Jp,C4) for every p ≥ 6 and the subscript p = n+3 of M., {"references":["Harju, T. (2011). Lecture Notes on GRAPH THEORY. [pdf handout]. Retrieved from BMEVISZAA02,University of Turku, Finland Online: http://cs.bme.hu/fcs/graphtheory.pdf","Parsons, T. D. (1975). Ramsey Graphs and Block Designs I. Transactions of the American Mathematical Society, 209(1), 33-44","Ezhilarasi, H. S., & Jesintha, J. J. (2012). Butterfl y Graphs with Shell Orders m and 2m+ 1 are Graceful. Bonfring International Journal of Research in Communication Engineering, 2(2), 1-5.","Zhang, Y., Broersma, H., & Chen, Y. (2014). A remark on star-C4 and wheel-C4 Ramsey numbers. Electronic Journal of Graph Theory and Applications (EJGTA), 2(2), 110-114."]}

We consider the concepts of a t-total vertex cover and a t-total edge cover (t ≥ 1),\ud which generalize the notions of a vertex cover and an edge cover, respectively. A ttotal\ud vertex (respectively edge) cover of a connected graph G is a vertex (edge) cover\ud S of G such that each connected component of the subgraph of G induced by S has\ud least t vertices (edges). These definitions are motivated by combining the concepts\ud of clustering and covering in graphs. Moreover they yield a spectrum of parameters\ud that essentially range from a vertex cover to a connected vertex cover (in the vertex\ud case) and from an edge cover to a spanning tree (in the edge case). For various values\ud of t, we present N P-completeness and approximability results (both upper and lower\ud bounds) and FPT algorithms for problems concerned with finding the minimum size\ud of a t-total vertex cover, t-total edge cover and connected vertex cover, in particular\ud improving on a previous FPT algorithm for the latter problem.