Finding partition with maximum number of edges between setsMean number of edges between two equal partitionsFinding edges with minimal weight sum, such that every simple cycle contain at least one edgegraph theory analogue of rectangular matrixMinimum number of sets of unreachable vertices for directed acyclic graph (DAG)Maximize the number of edges in subgraphmaximum matching number decreases when vertices collapse?What is the relationship between minimum vertex cover and minimum clique coverRemoving max number of edges while keeping minimum distancesOptimal partitioning of n-tuples
Are there any “Third Order” acronyms used in space exploration?
2000s space film where an alien species has almost wiped out the human race in a war
Assign every word from a line to a variable
Importance of the current postdoc advisor's letter in TT job search
What's the benefit of prohibiting the use of techniques/language constructs that have not been taught?
If I want an interpretable model, are there methods other than Linear Regression?
How would you control supersoldiers in a late iron-age society?
International Orange?
Why is belonging not transitive?
Ambiguity in notation resolved by +
Why any infinite sequence of real functions can be generated from a finite set through composition?
Is there any reason to concentrate on the Thunderous Smite spell after using its effects?
How clean are pets?
Wrong Schengen Visa exit stamp on my passport, who can I complain to?
Can a business put whatever they want into a contract?
Some Prime Peerage
Why is the car dealer insisting on a loan instead of cash?
How does a simple logistic regression model achieve a 92% classification accuracy on MNIST?
Test to know when to use GLM over Linear Regression?
'Overwrote' files, space still occupied, are they lost?
Can I see Harvest moon in India?
How To Make Earth's Oceans as Brackish as Lyr's
Why does an orbit become hyperbolic when total orbital energy is positive?
Insight into cavity resonators
Finding partition with maximum number of edges between sets
Mean number of edges between two equal partitionsFinding edges with minimal weight sum, such that every simple cycle contain at least one edgegraph theory analogue of rectangular matrixMinimum number of sets of unreachable vertices for directed acyclic graph (DAG)Maximize the number of edges in subgraphmaximum matching number decreases when vertices collapse?What is the relationship between minimum vertex cover and minimum clique coverRemoving max number of edges while keeping minimum distancesOptimal partitioning of n-tuples
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
Given a graph (say in adjacency list form), is there an algorithm to find a partition of vertices such that the number of edges between the two sets of the partition is the maximum possible?
For example, for the following set of edges of a graph with vertex set $1, 2, 3, 4, 5, 6$:
$(1, 2), (2, 3), (3, 1), (4, 5) , (5, 6), (6, 4)$, one possible "maximum" partition is $1, 3, 4, 6, 2, 5$ with $4$ edges between the sets $1, 3, 4, 6$ and $2, 5$.
graphs graph-theory partitions
asked 8 hours ago
ab123ab123
1577 bronze badges
$endgroup$
add a comment
|
$begingroup$
Given a graph (say in adjacency list form), is there an algorithm to find a partition of vertices such that the number of edges between the two sets of the partition is the maximum possible?
For example, for the following set of edges of a graph with vertex set $1, 2, 3, 4, 5, 6$:
$(1, 2), (2, 3), (3, 1), (4, 5) , (5, 6), (6, 4)$, one possible "maximum" partition is $1, 3, 4, 6, 2, 5$ with $4$ edges between the sets $1, 3, 4, 6$ and $2, 5$.
graphs graph-theory partitions
asked 8 hours ago
ab123ab123
1577 bronze badges
$endgroup$
add a comment
|
$begingroup$
Given a graph (say in adjacency list form), is there an algorithm to find a partition of vertices such that the number of edges between the two sets of the partition is the maximum possible?
For example, for the following set of edges of a graph with vertex set $1, 2, 3, 4, 5, 6$:
$(1, 2), (2, 3), (3, 1), (4, 5) , (5, 6), (6, 4)$, one possible "maximum" partition is $1, 3, 4, 6, 2, 5$ with $4$ edges between the sets $1, 3, 4, 6$ and $2, 5$.
graphs graph-theory partitions
asked 8 hours ago
ab123ab123
1577 bronze badges
$endgroup$
Given a graph (say in adjacency list form), is there an algorithm to find a partition of vertices such that the number of edges between the two sets of the partition is the maximum possible?
For example, for the following set of edges of a graph with vertex set $1, 2, 3, 4, 5, 6$:
$(1, 2), (2, 3), (3, 1), (4, 5) , (5, 6), (6, 4)$, one possible "maximum" partition is $1, 3, 4, 6, 2, 5$ with $4$ edges between the sets $1, 3, 4, 6$ and $2, 5$.
graphs graph-theory partitions
graphs graph-theory partitions
asked 8 hours ago
ab123ab123
1577 bronze badges
asked 8 hours ago
ab123ab123
1577 bronze badges
asked 8 hours ago
ab123ab123
1577 bronze badges
asked 8 hours ago
ab123ab123
1577 bronze badges
asked 8 hours ago
ab123ab123
1577 bronze badges
1577 bronze badges
add a comment
|
add a comment
|
1 Answer
1
active
oldest
votes
$begingroup$
If your question really is "is there an algorithm", the answer is obviously yes: just try every possible partition and choose the one maximizing the number of edges with endpoints in different parts.
Otherwise, it's unlikely that there is a polynomial-time algorithm. Indeed, this problem is known as maximum cut and it is well-known to be NP-hard.
answered 7 hours ago
JuhoJuho
16.8k5 gold badges43 silver badges93 bronze badges
$endgroup$
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%2f114754%2ffinding-partition-with-maximum-number-of-edges-between-sets%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$
If your question really is "is there an algorithm", the answer is obviously yes: just try every possible partition and choose the one maximizing the number of edges with endpoints in different parts.
Otherwise, it's unlikely that there is a polynomial-time algorithm. Indeed, this problem is known as maximum cut and it is well-known to be NP-hard.
answered 7 hours ago
JuhoJuho
16.8k5 gold badges43 silver badges93 bronze badges
$endgroup$
add a comment
|
$begingroup$
If your question really is "is there an algorithm", the answer is obviously yes: just try every possible partition and choose the one maximizing the number of edges with endpoints in different parts.
Otherwise, it's unlikely that there is a polynomial-time algorithm. Indeed, this problem is known as maximum cut and it is well-known to be NP-hard.
answered 7 hours ago
JuhoJuho
16.8k5 gold badges43 silver badges93 bronze badges
$endgroup$
add a comment
|
$begingroup$
If your question really is "is there an algorithm", the answer is obviously yes: just try every possible partition and choose the one maximizing the number of edges with endpoints in different parts.
Otherwise, it's unlikely that there is a polynomial-time algorithm. Indeed, this problem is known as maximum cut and it is well-known to be NP-hard.
answered 7 hours ago
JuhoJuho
16.8k5 gold badges43 silver badges93 bronze badges
$endgroup$
If your question really is "is there an algorithm", the answer is obviously yes: just try every possible partition and choose the one maximizing the number of edges with endpoints in different parts.
Otherwise, it's unlikely that there is a polynomial-time algorithm. Indeed, this problem is known as maximum cut and it is well-known to be NP-hard.
answered 7 hours ago
JuhoJuho
16.8k5 gold badges43 silver badges93 bronze badges
answered 7 hours ago
JuhoJuho
16.8k5 gold badges43 silver badges93 bronze badges
answered 7 hours ago
JuhoJuho
16.8k5 gold badges43 silver badges93 bronze badges
answered 7 hours ago
JuhoJuho
16.8k5 gold badges43 silver badges93 bronze badges
16.8k5 gold badges43 silver badges93 bronze badges
add a comment
|
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%2f114754%2ffinding-partition-with-maximum-number-of-edges-between-sets%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
