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
Impossible Scrabble Words
Can I see Harvest moon in India?
What are the advantages and disadvantages of tail wheels that cause modern airplanes to not use them?
Is there any reason to concentrate on the Thunderous Smite spell after using its effects?
What is the mathematical notation for rounding a given number to the nearest integer?
Does a large scratch in an ND filter affect image quality?
Extra initial Aeneid lines in 1662 M. de Marolles version
Pronunciation of "солнце"
Meaning of Swimming their horses
What is a "major country" as named in Bernie Sanders' Healthcare debate answers?
Why is my fire extinguisher emptied after one use?
What does "boys rule, girls drool" mean?
What was the motivation for the invention of electric pianos?
Importance of the current postdoc advisor's letter in TT job search
Expectation value of operators with non-zero Hamiltonian commutators
International Orange?
Output a Super Mario Image
Why is the car dealer insisting on a loan instead of cash?
Wrong Schengen Visa exit stamp on my passport, who can I complain to?
Shouldn't countries like Russia and Canada support global warming?
Is my sink P-trap too low?
Ethernet, Wifi and a little human psychology
Can an infinite series be thought of as adding up "infinitely many" terms?
Block diagram vs flow chart?
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
1627 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
1627 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
1627 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
1627 bronze badges
asked 8 hours ago
ab123ab123
1627 bronze badges
asked 8 hours ago
ab123ab123
1627 bronze badges
asked 8 hours ago
ab123ab123
1627 bronze badges
asked 8 hours ago
ab123ab123
1627 bronze badges
1627 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 8 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 8 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 8 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 8 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 8 hours ago
JuhoJuho
16.8k5 gold badges43 silver badges93 bronze badges
answered 8 hours ago
JuhoJuho
16.8k5 gold badges43 silver badges93 bronze badges
answered 8 hours ago
JuhoJuho
16.8k5 gold badges43 silver badges93 bronze badges
answered 8 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
