Maximum-cardinality matching in unbalanced bipartite graphsExistence of bipartite perfect matchingmaximum bipartite matchingVertex cover in bipartite graph from Hopcroft-Karp AlgorithmMaximum bipartite matching when some nodes must be matchedWhy is bipartite graph matching hard?Understanding characterizations of Matching on GraphsMore efficient maximum bipartite matching
A Pixelated Sequence - Find the Continuation
What if I don't know whether my program will be linked to a GPL library or not?
Can a business put whatever they want into a contract?
Unpredictability of Stock Market
Who are the people reviewing far more papers than they're submitting for review?
Why does an orbit become hyperbolic when total orbital energy is positive?
Should I inform my future product owner that there are big chances that a team member will leave the company soon?
What does the "capacitor into resistance" symbol mean?
Why does '/' contain '..'?
Why does dd not make working bootable USB sticks for Microsoft?
Why cannot a convert make certain statements? I feel they are being pushed away at the same time respect is being given to them
How to make classical firearms effective on space habitats despite the coriolis effect?
How to choose a power source for Raspberry Pi 4?
Maximum-cardinality matching in unbalanced bipartite graphs
Tips for remembering the order of parameters for ln?
Python web-scraper to download table of transistor counts from Wikipedia
What is the source of "You can achieve a lot with hate, but even more with love" (Shakespeare?)
Random restarts for unsatisfiable problems
Wrong Schengen Visa exit stamp on my passport, who can I complain to?
Did Sauron ever betray Morgoth?
Impossible Scrabble Words
How to give my students a straightedge instead of a ruler
Amortized Loans seem to benefit the bank more than the customer
What is the origin of the "being immortal sucks" trope?
Maximum-cardinality matching in unbalanced bipartite graphs
Existence of bipartite perfect matchingmaximum bipartite matchingVertex cover in bipartite graph from Hopcroft-Karp AlgorithmMaximum bipartite matching when some nodes must be matchedWhy is bipartite graph matching hard?Understanding characterizations of Matching on GraphsMore efficient maximum bipartite matching
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$.
The Hopcroft-Karp algorithm runs in time $O(|E|sqrt)$, where here $|V| = |X|+|Y|$. So if the graph is unbalanced and $|X|<|Y|$, the run-time is $O(|E|sqrt)$.
Is there an algorithm that attains a better worst-case runtime complexity for the case of an unbalanced bipartite graph, where $|X| in o(|Y|)$? In particular, if $|X|$ is constant, is it possible to get run-time $O(|E|)$?
optimization reference-request runtime-analysis bipartite-matching
asked 8 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
$endgroup$
add a comment
|
$begingroup$
Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$.
The Hopcroft-Karp algorithm runs in time $O(|E|sqrt)$, where here $|V| = |X|+|Y|$. So if the graph is unbalanced and $|X|<|Y|$, the run-time is $O(|E|sqrt)$.
Is there an algorithm that attains a better worst-case runtime complexity for the case of an unbalanced bipartite graph, where $|X| in o(|Y|)$? In particular, if $|X|$ is constant, is it possible to get run-time $O(|E|)$?
optimization reference-request runtime-analysis bipartite-matching
asked 8 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
$endgroup$
add a comment
|
$begingroup$
Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$.
The Hopcroft-Karp algorithm runs in time $O(|E|sqrt)$, where here $|V| = |X|+|Y|$. So if the graph is unbalanced and $|X|<|Y|$, the run-time is $O(|E|sqrt)$.
Is there an algorithm that attains a better worst-case runtime complexity for the case of an unbalanced bipartite graph, where $|X| in o(|Y|)$? In particular, if $|X|$ is constant, is it possible to get run-time $O(|E|)$?
optimization reference-request runtime-analysis bipartite-matching
asked 8 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
$endgroup$
Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$.
The Hopcroft-Karp algorithm runs in time $O(|E|sqrt)$, where here $|V| = |X|+|Y|$. So if the graph is unbalanced and $|X|<|Y|$, the run-time is $O(|E|sqrt)$.
Is there an algorithm that attains a better worst-case runtime complexity for the case of an unbalanced bipartite graph, where $|X| in o(|Y|)$? In particular, if $|X|$ is constant, is it possible to get run-time $O(|E|)$?
optimization reference-request runtime-analysis bipartite-matching
optimization reference-request runtime-analysis bipartite-matching
asked 8 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
asked 8 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
asked 8 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
asked 8 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
asked 8 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
2,60713 silver badges44 bronze badges
add a comment
|
add a comment
|
1 Answer
1
active
oldest
votes
$begingroup$
I just found the answer myself. In this paper:
Lyle Ramshaw, Robert E. Tarjan (2012). "On minimum-cost assignments in unbalanced bipartite graphs". Technical reports, HP research labs.
in section 5, the authors show that the Hopcroft-Karp algorithm in fact solves the following problem: given an integer $s$, find matchings with $1,ldots,s$ edges. The run-time is $O(|E|sqrts)$. In particular, if $|X|<|Y|$, we can take $s=|X|$ and the run-time is $O(|E|sqrtX)$.
answered 7 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
$endgroup$
$begingroup$
I would suggest this link arxiv.org/abs/1904.11244 as an additional note on parameterized matching. It proves square root dependence on many parameters, i.e. $O(|E|sqrt k)$, for different parameters $k$.
$endgroup$
– narek Bojikian
2 hours ago
add a comment
|
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f114779%2fmaximum-cardinality-matching-in-unbalanced-bipartite-graphs%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I just found the answer myself. In this paper:
Lyle Ramshaw, Robert E. Tarjan (2012). "On minimum-cost assignments in unbalanced bipartite graphs". Technical reports, HP research labs.
in section 5, the authors show that the Hopcroft-Karp algorithm in fact solves the following problem: given an integer $s$, find matchings with $1,ldots,s$ edges. The run-time is $O(|E|sqrts)$. In particular, if $|X|<|Y|$, we can take $s=|X|$ and the run-time is $O(|E|sqrtX)$.
answered 7 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
$endgroup$
$begingroup$
I would suggest this link arxiv.org/abs/1904.11244 as an additional note on parameterized matching. It proves square root dependence on many parameters, i.e. $O(|E|sqrt k)$, for different parameters $k$.
$endgroup$
– narek Bojikian
2 hours ago
add a comment
|
$begingroup$
I just found the answer myself. In this paper:
Lyle Ramshaw, Robert E. Tarjan (2012). "On minimum-cost assignments in unbalanced bipartite graphs". Technical reports, HP research labs.
in section 5, the authors show that the Hopcroft-Karp algorithm in fact solves the following problem: given an integer $s$, find matchings with $1,ldots,s$ edges. The run-time is $O(|E|sqrts)$. In particular, if $|X|<|Y|$, we can take $s=|X|$ and the run-time is $O(|E|sqrtX)$.
answered 7 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
$endgroup$
$begingroup$
I would suggest this link arxiv.org/abs/1904.11244 as an additional note on parameterized matching. It proves square root dependence on many parameters, i.e. $O(|E|sqrt k)$, for different parameters $k$.
$endgroup$
– narek Bojikian
2 hours ago
add a comment
|
$begingroup$
I just found the answer myself. In this paper:
Lyle Ramshaw, Robert E. Tarjan (2012). "On minimum-cost assignments in unbalanced bipartite graphs". Technical reports, HP research labs.
in section 5, the authors show that the Hopcroft-Karp algorithm in fact solves the following problem: given an integer $s$, find matchings with $1,ldots,s$ edges. The run-time is $O(|E|sqrts)$. In particular, if $|X|<|Y|$, we can take $s=|X|$ and the run-time is $O(|E|sqrtX)$.
answered 7 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
$endgroup$
I just found the answer myself. In this paper:
Lyle Ramshaw, Robert E. Tarjan (2012). "On minimum-cost assignments in unbalanced bipartite graphs". Technical reports, HP research labs.
in section 5, the authors show that the Hopcroft-Karp algorithm in fact solves the following problem: given an integer $s$, find matchings with $1,ldots,s$ edges. The run-time is $O(|E|sqrts)$. In particular, if $|X|<|Y|$, we can take $s=|X|$ and the run-time is $O(|E|sqrtX)$.
answered 7 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
answered 7 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
answered 7 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
answered 7 hours ago
Erel Segal-HaleviErel Segal-Halevi
2,60713 silver badges44 bronze badges
2,60713 silver badges44 bronze badges
$begingroup$
I would suggest this link arxiv.org/abs/1904.11244 as an additional note on parameterized matching. It proves square root dependence on many parameters, i.e. $O(|E|sqrt k)$, for different parameters $k$.
$endgroup$
– narek Bojikian
2 hours ago
add a comment
|
$begingroup$
I would suggest this link arxiv.org/abs/1904.11244 as an additional note on parameterized matching. It proves square root dependence on many parameters, i.e. $O(|E|sqrt k)$, for different parameters $k$.
$endgroup$
– narek Bojikian
2 hours ago
$begingroup$
I would suggest this link arxiv.org/abs/1904.11244 as an additional note on parameterized matching. It proves square root dependence on many parameters, i.e. $O(|E|sqrt k)$, for different parameters $k$.
$endgroup$
– narek Bojikian
2 hours ago
$begingroup$
I would suggest this link arxiv.org/abs/1904.11244 as an additional note on parameterized matching. It proves square root dependence on many parameters, i.e. $O(|E|sqrt k)$, for different parameters $k$.
$endgroup$
– narek Bojikian
2 hours ago
add a comment
|
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f114779%2fmaximum-cardinality-matching-in-unbalanced-bipartite-graphs%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
