The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
A transposition graph is a Cayley graph in which each vertex corresponds to a permutation and an edge is placed between permutations iff they differ by exactly one transposition. In this article, we propose an efficient algorithm to find a collection of vertex‐disjoint paths connecting a given source vertex s and a given set of destination vertices D. The running time of the algorithm is polynomial...
Ryser's conjecture postulates that for r ‐partite hypergraphs, τ ≤ (r ‐ 1)ν where τ is the covering number of the hypergraph and ν is the matching number. Although this conjecture has been open since the 1960s, researchers have resolved it for special cases such as for intersecting hypergraphs where r ≤ 5. In this article, we prove several results pertaining to matchings and coverings in r ‐partite...
We study perfect matchings in graphs that have the two properties of being robust as well as recoverable; where robust means that the failure of a set of not too many edges of can be compensated, and recoverable means that this compensation can be done in an efficient way, that is, has a perfect matching for which the symmetric difference of and is small. We establish...
We study online secretary problems with returns in combinatorial packing domains with n candidates that arrive sequentially over time in random order. The goal is to determine a feasible packing of candidates of maximum total value. In the first variant, each candidate arrives exactly twice. All 2n arrivals occur in random order. We propose a simple 0.5‐competitive algorithm. For the online bipartite...
Matchings and T‐joins are fundamental and much‐studied concepts in graph theory and combinatorial optimization. One important application of matchings and T‐joins is in the computation of strong lower bounds for arc routing problems (ARPs). An ARP is a special kind of vehicle routing problem, in which the demands are located along edges or arcs, rather than at nodes. We point out that the literature...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.