A matching (aka **Independent Edge Set**) in a simple graph is the set of pairwise non-adjacent edges i.e. no two edges have common vertex.

learn more… | top users | synonyms

0
votes
0answers
14 views

Problem with Blossoms while searching for augmenting pathes

I have problems understanding the effect of Blossoms while searching for augmenting pathes (in the matching problem). If I have the following graph Can't I find the augmented path from n1 to n13? ...
0
votes
1answer
35 views

Stable matching with constraints

I'm reading through Algorithm Design by Kleinberg and Tardos and was working on Ch1 Q1. The question is about stable matching and their 'proof' is presented by contradiction. I have an alternative ...
0
votes
0answers
24 views

Is maximum size of graph matching equal to maximum size of its dual graph matching?

This is really puzzling me! A hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a subset of $V$. A ...
2
votes
2answers
92 views

Finding perfect matchings with as few database queries as possible

I am trying to research a problem similar to the stable matching problem with a few different rules. The problem is as follows: There are an equal number of men and women. Each man has a perfect ...
2
votes
1answer
49 views

Equality of cardinality of maximum matching and minimum vertex cover in general

I'm preparing for exam and I came across this problem: We say that a graph is König's graph when the sizes of its minimum vertex cover and maximum matching are equal. Find a polynomial time ...
3
votes
0answers
13 views

Set of vertex-disjoint cycles maximizing different colored vertices

Let $G=(V,E)$ be a directed graph whose vertices $v \in V$ have colors and its edges $e\in E$ have costs $cost(e)$. I am looking to find a set of vertex-disjoint cycles that: First maximizes the ...
0
votes
0answers
23 views

Algorithm for assignment of workers to non-overlapping subsets

I am curious if there is an efficient solution to the following variant of the linear sum assignment. For example, can it be modelled as a matching problem or linear program? I have a finite quantity ...
3
votes
1answer
21 views

Woman optimal Gale Shapley Stable Matching

I am learning about Gale Shapley Algorithm now, and I understand that it is Man Optimal and that all possible executions will yield a stable matching where each man gets the best partner that he can ...
1
vote
1answer
35 views

A condition ensuring that a bipartite graph have a perfect matching

There is a bipartite graph $G=(A,B,E)$ such that for every edge $(a,b)$ (where $a$ comes from $A$ and $b$ from $B$), $\deg(a) \geq \deg(b)$, and additionally $\deg(a) \geq 1$ for all $a \in A$. From ...
3
votes
0answers
51 views

Complexity class of a counting problem

Consider the following inequalities: $\sum_j a_{ij}x_{ij}=1 \;\;\; i=1,...,n$ $\sum_i a_{ij}x_{ij} \le y_i \;\;\; j=1,...,n$ $x_{ij} \ge 0 \;\;\; i,j=1,...,n$ $y_i \in \{0,1,2\} \,\,\,\, i=1,...,...
-1
votes
1answer
47 views

Is the maximum matching problem trivial when the graph is complete?

I have a quick question. The maximum matching problem is an easy problem but not a trivial one. I was wondering that if the bipartite graph was complete, is it a trivial problem? I think we can just ...
2
votes
0answers
89 views

Vertex-disjoint cycles passing through a collection of vertices

I am wondering about the complexity of the following problem: given a directed graph $G=(V,E)$ (which may have self-loops at some vertices) and a subset of the vertices $U \subset V$, does there exist ...
0
votes
0answers
16 views

How do I show that the matching polytope of $K_{2n}$ is a linear projection of the perfect matching polytope of $K_n$?

Of course a matching polytope is the convex hull of edges in a matching and similarly for a perfect matching polytope.
2
votes
1answer
768 views

Perfect matching in a graph and complete matching in bipartite graph

When I google for complete matching, first link points to perfect matching on wolfram. It defines perfect matching as follows: A perfect matching of a graph is a matching (i.e., an independent ...
3
votes
1answer
98 views

Why is Savage's Vertex Cover algorithm a 2-approximation?

Carla. D. Savage formulated the following approximation algorithm for the vertex cover problem. Given graph $G$, start at arbitrary node and traverse $G$ depth-first Obtain DFS tree $T$ ...
3
votes
0answers
122 views

Construct matching for half of the vertices, in linear time

Suppose we have a graph $G=(V,E)$ connected and $K_{1,3}$-free. Sumner proved that every claw-free connected graph with an even number of vertices has a perfect matching (so, it is maximum matching). ...
1
vote
1answer
103 views

Assignment based on ranked preference

Assume that there are n students, who have to be evenly assigned to m groups. For every student, a preference ranking of of the <...
1
vote
1answer
75 views

Bit-parallelism and NFA simulation

In several papers I have read that Bit-parallel pattern matching is an NFA-simulation. My questions are: 1- Is it true in general? Or, is there any restrictions? 2- As any regular expression can be ...
9
votes
0answers
182 views

How fast can we compute the size of maximum matching in an unweighted bipartite graph?

Is there a way to compute the size of a maximum matching in an unweighted bipartite graph more efficiently (e.g. faster) than computing a maximum matching? It is a long shot but it is often ...
2
votes
1answer
55 views

Computing optimal assignments using little memory

I have two lists where each item in the first list has a rating for each item in the second. I need to determine an optimal matching (or the best x scenarios) where items are matched, but each item ...
1
vote
0answers
61 views

Matching elements of two sequences: choosing the best one

I have the following problem. Let $P$ and $Q$ be two ordered sequences of time instants. $[p_0,p_1,\ldots,p_n]$ and $[q_0,q_1,\ldots,q_m]$ are the elements of $P$ and $Q$ respectively. A first ...
1
vote
2answers
80 views

NFA-style representation of regexps which includes AND

I'm looking for a regexp matching strategy that supports conjunction and which is based on an NFA-style machine. I know how to handle conjunctions using a DFA, or using Brzozowski's approach, but for ...
0
votes
0answers
22 views

Effect of mismatches on string matching finite automata

I am contemplating a string matching FA algorithm (not KMP). The complexity of its transition function calculation ie the preprocessing is m(length of pattern )* (the language of the FA) . What effect ...
1
vote
1answer
49 views

Similarity of two monochromatic shapes

I need to find out to what extent two shapes are similar. I mean I've got two vectors of points - and just that, no shadows, color or whatever - simplest case. Two triangles are the perfect example. ...
2
votes
1answer
29 views

About having analytic control over any algorithm which finds perfect matchings.

A trivial algorithm to decompose a degree-d (n,n)-bipartite graph into d disjoint perfect matchings is this : direct all the edges from left to right and put capacity one on each of them - then add a ...
3
votes
1answer
985 views

Find perfect matching whose weight is minimal, in polynomial time

Given a bipartite graph $G=(A,B,E)$ and a weight function $w: E \rightarrow\mathbb{R}^+$, I'd like to find a perfect matching $M\subseteq E$ with min. weight. I'm assuming $|A| \leq |B|$, and WLOG $G$ ...
0
votes
1answer
383 views

Gale–Shapley algorithm is man-optimal

I am trying to understand the proof why Gale–Shapley algorithm is optimal, however i am unable to do so. Could you please expand the proof, since the proof on this page https://sites.google.com/site/...
1
vote
1answer
275 views

How to do high performance string matching when comparing unordered sets of tokens [closed]

This is the problem: I have some strings stored in the database. Each of the strings can be seen as a set of tokens separated by comma with no repetition (I mean a token cannot appear more than one ...
-1
votes
1answer
48 views

Stable marriage problem with more people then priorizations [closed]

I am trying to solve a stable marriage problem where I have e.g. 20 women and 20 men, but they always only prioritise 4 pre-selected people of the opposite sex. My algorithm distributes all men and ...
1
vote
0answers
59 views

Using A* to find the word closest to an input rejected by a finite automaton

In the article Fast approximate string matching with finite automata by M. Hulden (2009) (mostly pages 58/59), the author describes how to search for a closest matching string word from an automaton ...
2
votes
1answer
662 views

Stable marriage problem with only one side having preferences [duplicate]

I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and ...
2
votes
1answer
60 views

Could an alternating approach yield a fairer solution to the stable marriage problem?

With the G-S algorithm solution to the stable marriage problem, the proposers get the best possible stable matches, while the reviewers get the worst possible stable matches. This is because the ...
5
votes
1answer
94 views

Finding a perfect matching using an LP

I have a basic question about the power of Linear Programming that has been bothering me for some time. I believe there is something simple I am missing. Linear Programming is $\mathsf{P}$-complete, ...
1
vote
0answers
132 views

Finding the number of distinct maximal matching in a bipartite graph [closed]

In a bipartite graph, how can we find the total number of ways of getting a maximal matching? The cardinality of both the sets in the bipartite graph may not be the same. So two matchings are said to ...
0
votes
1answer
77 views

Algorithm for distributing members over activites (with individual preferences)

So in my school we have a day where everybody participates in different activities. Each projects can have like 10 members. The whole day is divided in 2 or 3 different blocks, in which the pupils ...
6
votes
1answer
304 views

Complexity of Hopcroft-Karp

I have a rather basic question about the number of operations taken by the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph. It is commonly reported as $O(m \sqrt{n})$ where ...
1
vote
2answers
153 views

Algorithm to match timestamped events from two sources

does a good known algorithm exists for this problem? On input I have two series of timestamps "when the event was observed". Theoretically the recorded timestamps should be very well aligned. ...
1
vote
1answer
353 views

Why can't we solve the dinner party problem by finding a maximum matching?

Consider the following dinner party problem: Given a list of acquaintances, and a list containing all pairs of individuals who are not on speaking terms with each other, find the largest set of ...
0
votes
3answers
120 views

Bipartite Matching in the Plane

I'm currently working on a problem that I came across: You are given a set $B$ of $n$ points in the plane, and a set $R$ of $n$ points in the plane. Each point is given by its coordinates. I have ...
5
votes
1answer
495 views

How are REGEXP implemented in programming languages?

Is there a good general paper about the interpretation or compilation of REGEXP in programming languages for pattern matching, with or without variables? I am not looking for a quick explanation about ...
1
vote
1answer
80 views

Are algorithms for searching text vs searching numbers fundamentally different?

I face this problem a lot while searching phone numbers and bank account numbers, when I do remember it partially. I save a draft in gmail with the content ...
4
votes
2answers
251 views

How do I choose an optimal cell size when searching for close pairs of points, and using cells to implement this?

Suppose that I have a set of $N$ points in $k$-dimensional space ($k>1$), such as in this question, and that I need to find all pairs with a distance¹ smaller than a certain threshold $t$. The ...
3
votes
0answers
63 views

variant of the stable roommates problem

The Stable Roommates Problem matches 2n participants into n sets of roommates based off of each participant's list of preferences. I was wondering if there was a variant of this problem where the ...
2
votes
1answer
194 views

Degree conditions sufficient for Hall's theorem

Let $G=(L,R,E)$ be a bipartite graph, are there conditions on the degree of the vertices under which the condition of Hall's theorem is surely satisfied? (meaning a perfect matching exists in the ...
2
votes
1answer
89 views

What's the dual problem of stable matching?

So the dual problem of max-flow is min-cut. What's the dual problem of stable matching?
4
votes
1answer
2k views

Counting and finding all perfect/maximum matchings in general graphs

Recently i've been dealing with a problem that led me to the following questions: Is there a good algorithm to enumerate all maximum/perfect matchings in a general graph? Is there a good algorithm ...
2
votes
1answer
78 views

Number of Matchings in a Bipartite

Given two sets A and B of sizes |A| = n and |B| = m, where m >= n. There are edges from set A to set B. I need to find the number of matchings where all of vertices ...
2
votes
2answers
921 views

Confusion about finite automata construction in Knuth–Morris–Pratt algorithm

There is one point I don't understand in the DFA construction for mismatch cases. Here is the lecture note I watched, which describes how to handle mismatched characters during the DFA construction ...
0
votes
1answer
169 views

Is there a formula to state the number of 'sets' of 'ordered sets within ordered groups'?

I am new to this and an amateur... please help. My Question in practical terms: Given The three following inputs... determine the number of unique group arrangements as an ordered set. INPUT: 'a' = ...
2
votes
0answers
76 views

Hardness of a special case of maximum matching

Input: A set of $n$ Users $U=\{u_1, ..., u_n\}$ and a set of $m$ products $I=\{i_1, ..., i_m\}$. Associated with each pair $u \in U$ and $i \in I$ is the probability $p_{u,i}$ of $u$ purchasing the ...