Suppose that each member of a set A applicants ranks subset P posts in an order preference, possibly involving ties. matching is (applicant, post) pairs such applicant and post appears at most one pair. rank-maximal which the maximum possible number are matched to their first choice post, subject condition, second so on. This relevant concept any practical situation it was studied by Irving [2003].We give algorithm compute with running time O (min( n + C , √ ) m ), where maximal rank edge...

We give a 3 2 -approximation algorithm for finding stable matchings that runs in O(m) time. The previous most well-known algorithm, by McDermid, has the same approximation ratio but O(n3/2m) time, where n denotes number of people andm is total length preference lists given instance. In addition, and analysis are much simpler. also extension computing many-to-many matchings.

We consider the problem of computing a minimum cycle basis an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, {0,1} incidence vector is associated each space over $\mathbb{F}_{2}$ generated by these vectors G. A set cycles called if it forms for its space. where sum weights Minimum are useful in number contexts, e.g. analysis electrical networks structural engineering. The previous best algorithm has running time O(m ω n), exponent matrix...

An instance of the stable marriage problem is an undirected bipartite graph G = ( X ∪ W , E ) with linearly ordered adjacency lists ties allowed in ordering. A matching M a set edges, no two which share endpoint. edge e b ∈ ∖ blocking for if either unmatched or strictly prefers to its partner and unmatched, indifferent between them. strongly there respect it. We give O nm algorithm computing matchings, where n number vertices m edges. The previous best had running time 2 ). also study this...

In the maximum asymmetric traveling salesman problem (Max ATSP) we are given a complete directed graph with nonnegative weights on edges and wish to compute tour of weight. this paper give fast combinatorial $\frac 34$-approximation algorithm for Max ATSP. It is based novel use {\it half-edges}, matchings new method edge coloring. (A half-edge} $(u,v)$ informally speaking "either head or tail $(u,v)$".) The current best approximation algorithms ATSP, achieving guarantee 23$, due Kaplan,...

We give faster and simpler approximation algorithms for the (1,2)-TSP problem, a well-studied variant of traveling salesperson problem where all distances between cities are either 1 or 2. Our main results two (1,2)-TSP, one with factor 8/7 run time O(n^3) other having an guarantee 7/6 O(n^{2.5}). The 8/7-approximation matches best known due to Berman Karpinski (SODA 2006), but considerably improves previous O(n^9). Thus, ours is first improvement in more than 10 years. algorithm based on...

Suppose that each member of a set A applicants ranks subset P posts in an order preference, possibly involving ties. matching is (applicant, post) pairs such applicant and post appears at most one pair. greedy which the maximum possible number are matched to their first choice post, subject condition, second so on. This relevant concept any practical situation it was studied by Irving [8].We define bipartite graph G = (A U P,e), where e consists all (a, p) p preference list a. Each edge has...

Suppose that each member of a set agents has preference list subset houses, possibly involving ties, and agent house their capacity denoting the maximum number houses/agents (respectively) can be matched to him/her/it. We want find matching M, called popular, for which there is no other M′ such more prefer M than M′, subject suitable definition "prefers". In above problem uses exactly one vote compare two matchings. we consider in paper votes equal capacity. Given matchings an compares best...

An instance of a strongly stable matching problem (SSMP) is an undirected bipartite graph G = (A ∪ B, E), with adjacency list each vertex being linearly ordered ties, which are subsets vertices equally good for given vertex. Ties disjoint and may contain one A M set vertex-disjoint edges. edge (x, y) ∊ E\M blocking if x either unmatched or strictly prefers y to its current partner in M, indifferent between them. there no respect it. We present characterisation the all matchings, thus solving...

An instance of a strongly stable matching problem (SSMP) is an undirected bipartite graph G = (A∪B, E), with adjacency list each vertex being linearly ordered ties, which are subsets vertices equally good for given vertex. Ties disjoint and may contain one A M set vertex-disjoint edges. edge (x, y) ∈ E\M blocking if x either unmatched or strictly prefers y to its current partner in M, indifferent between them. there no respect it. We present characterisation the all matchings, thus solving...

We consider problems of finding a maximum size/weight $t$-matching without forbidden subgraphs in an undirected graph $G$ with the degree bounded by $t+1$, where $t$ is integer greater than $2$. Depending on variant denote certain subsets $t$-regular complete partite $G$. A if there exists partition its vertex set such that every pair vertices from different sets connected edge and same form independent set. clique $K_t$ bipartite $K_{t,t}$ are examples graphs. These natural generalizations...