How to optimize the algorithm to find the max_depth_contact_series in a time varying graph?
Assuming there is a time varying graph with N nodes named a1,a2,...,an and contact series as t node1 node2 meaning node1 contacts with node2 at time t
Assuming node a1 carries a message(there is only one copy of the message in the graph), from time 0, how many nodes can the message contact with at most in time T? The message can be transferred to another node freely at anytime. For example, a1 can chose to transfer it to a2 at time 2 or keeps the message until a1 contacts with a3 and transfers it to a3.
Here is an example to make it more clear. For a graph with 6 nodes and contact series:
1 a1 a2
2 a1 a3
3 a1 a4
4 a3 a5
6 a3 a6
10 a4 a3
During time 0~10 the message can contact with 4 nodes at most:a2,a3,a5,a6 with message tranferred from a1 to a3 at time 2.
Keep in mind the time series. Here a1 carries the message but transfers the message to a3 at time 2. Then at time 3 node a1 has no message so the message cant contact with a4. If a1 keeps message at time 2 instead of tranferring to a3, the message contacts with the list a2,a3,a4,a3. The contact set will be {a2,a3,a4} with size 3 which is smaller than 4.
How can I get the largest contact nodes set? Or just the number?
At present I get it with recursive algorithm but the cost is unbearable when T is large.
algorithm data-structures graph graph-theory graph-algorithm
asked Nov 19 '18 at 7:40
oleotigeroleotiger
237
add a comment |
Assuming there is a time varying graph with N nodes named a1,a2,...,an and contact series as t node1 node2 meaning node1 contacts with node2 at time t
Assuming node a1 carries a message(there is only one copy of the message in the graph), from time 0, how many nodes can the message contact with at most in time T? The message can be transferred to another node freely at anytime. For example, a1 can chose to transfer it to a2 at time 2 or keeps the message until a1 contacts with a3 and transfers it to a3.
Here is an example to make it more clear. For a graph with 6 nodes and contact series:
1 a1 a2
2 a1 a3
3 a1 a4
4 a3 a5
6 a3 a6
10 a4 a3
During time 0~10 the message can contact with 4 nodes at most:a2,a3,a5,a6 with message tranferred from a1 to a3 at time 2.
Keep in mind the time series. Here a1 carries the message but transfers the message to a3 at time 2. Then at time 3 node a1 has no message so the message cant contact with a4. If a1 keeps message at time 2 instead of tranferring to a3, the message contacts with the list a2,a3,a4,a3. The contact set will be {a2,a3,a4} with size 3 which is smaller than 4.
How can I get the largest contact nodes set? Or just the number?
At present I get it with recursive algorithm but the cost is unbearable when T is large.
algorithm data-structures graph graph-theory graph-algorithm
asked Nov 19 '18 at 7:40
oleotigeroleotiger
237
Not clear whya4is not in the result list. Looks like a simple diffusion algorithm, so to maintain a set of contacted node from time to time seems to be very simple. Could you please clarify ?
– Jean-Baptiste Yunès
Nov 19 '18 at 8:34
I have re-edit the question to make it clear.
– oleotiger
Nov 19 '18 at 10:48
No that's not clear. Why at 3 a1 doesn't have the message? At 1, it already gave it to a2 so why is it available at 2??? Seems to be inconsistent
– Jean-Baptiste Yunès
Nov 19 '18 at 11:58
The node with message can decide when to transfer the message.a1can tranfer the message at time1or2or3or any time when there is a contact with another node. The purpose is to maximize the number of node which contacts with the message.
– oleotiger
Nov 19 '18 at 15:16
Ok then as I understand the problem is the longest path problem. That problem is known as NP-hard, which means that there is probably no efficient algorithm to solve it. It may exists some more efficient algorithms is your graph has some peculiar properties.
– Jean-Baptiste Yunès
Nov 19 '18 at 20:07
add a comment |
Assuming there is a time varying graph with N nodes named a1,a2,...,an and contact series as t node1 node2 meaning node1 contacts with node2 at time t
Assuming node a1 carries a message(there is only one copy of the message in the graph), from time 0, how many nodes can the message contact with at most in time T? The message can be transferred to another node freely at anytime. For example, a1 can chose to transfer it to a2 at time 2 or keeps the message until a1 contacts with a3 and transfers it to a3.
Here is an example to make it more clear. For a graph with 6 nodes and contact series:
1 a1 a2
2 a1 a3
3 a1 a4
4 a3 a5
6 a3 a6
10 a4 a3
During time 0~10 the message can contact with 4 nodes at most:a2,a3,a5,a6 with message tranferred from a1 to a3 at time 2.
Keep in mind the time series. Here a1 carries the message but transfers the message to a3 at time 2. Then at time 3 node a1 has no message so the message cant contact with a4. If a1 keeps message at time 2 instead of tranferring to a3, the message contacts with the list a2,a3,a4,a3. The contact set will be {a2,a3,a4} with size 3 which is smaller than 4.
How can I get the largest contact nodes set? Or just the number?
At present I get it with recursive algorithm but the cost is unbearable when T is large.
algorithm data-structures graph graph-theory graph-algorithm
asked Nov 19 '18 at 7:40
oleotigeroleotiger
237
Assuming there is a time varying graph with N nodes named a1,a2,...,an and contact series as t node1 node2 meaning node1 contacts with node2 at time t
Assuming node a1 carries a message(there is only one copy of the message in the graph), from time 0, how many nodes can the message contact with at most in time T? The message can be transferred to another node freely at anytime. For example, a1 can chose to transfer it to a2 at time 2 or keeps the message until a1 contacts with a3 and transfers it to a3.
Here is an example to make it more clear. For a graph with 6 nodes and contact series:
1 a1 a2
2 a1 a3
3 a1 a4
4 a3 a5
6 a3 a6
10 a4 a3
During time 0~10 the message can contact with 4 nodes at most:a2,a3,a5,a6 with message tranferred from a1 to a3 at time 2.
Keep in mind the time series. Here a1 carries the message but transfers the message to a3 at time 2. Then at time 3 node a1 has no message so the message cant contact with a4. If a1 keeps message at time 2 instead of tranferring to a3, the message contacts with the list a2,a3,a4,a3. The contact set will be {a2,a3,a4} with size 3 which is smaller than 4.
How can I get the largest contact nodes set? Or just the number?
At present I get it with recursive algorithm but the cost is unbearable when T is large.
algorithm data-structures graph graph-theory graph-algorithm
algorithm data-structures graph graph-theory graph-algorithm
asked Nov 19 '18 at 7:40
oleotigeroleotiger
237
asked Nov 19 '18 at 7:40
oleotigeroleotiger
237
edited Nov 19 '18 at 15:14
oleotiger
asked Nov 19 '18 at 7:40
oleotigeroleotiger
237
asked Nov 19 '18 at 7:40
oleotigeroleotiger
237
asked Nov 19 '18 at 7:40
oleotigeroleotiger
237
237
Not clear whya4is not in the result list. Looks like a simple diffusion algorithm, so to maintain a set of contacted node from time to time seems to be very simple. Could you please clarify ?
– Jean-Baptiste Yunès
Nov 19 '18 at 8:34
I have re-edit the question to make it clear.
– oleotiger
Nov 19 '18 at 10:48
No that's not clear. Why at 3 a1 doesn't have the message? At 1, it already gave it to a2 so why is it available at 2??? Seems to be inconsistent
– Jean-Baptiste Yunès
Nov 19 '18 at 11:58
The node with message can decide when to transfer the message.a1can tranfer the message at time1or2or3or any time when there is a contact with another node. The purpose is to maximize the number of node which contacts with the message.
– oleotiger
Nov 19 '18 at 15:16
Ok then as I understand the problem is the longest path problem. That problem is known as NP-hard, which means that there is probably no efficient algorithm to solve it. It may exists some more efficient algorithms is your graph has some peculiar properties.
– Jean-Baptiste Yunès
Nov 19 '18 at 20:07
add a comment |
Not clear whya4is not in the result list. Looks like a simple diffusion algorithm, so to maintain a set of contacted node from time to time seems to be very simple. Could you please clarify ?
– Jean-Baptiste Yunès
Nov 19 '18 at 8:34
I have re-edit the question to make it clear.
– oleotiger
Nov 19 '18 at 10:48
No that's not clear. Why at 3 a1 doesn't have the message? At 1, it already gave it to a2 so why is it available at 2??? Seems to be inconsistent
– Jean-Baptiste Yunès
Nov 19 '18 at 11:58
The node with message can decide when to transfer the message.a1can tranfer the message at time1or2or3or any time when there is a contact with another node. The purpose is to maximize the number of node which contacts with the message.
– oleotiger
Nov 19 '18 at 15:16
Ok then as I understand the problem is the longest path problem. That problem is known as NP-hard, which means that there is probably no efficient algorithm to solve it. It may exists some more efficient algorithms is your graph has some peculiar properties.
– Jean-Baptiste Yunès
Nov 19 '18 at 20:07
Not clear why
a4 is not in the result list. Looks like a simple diffusion algorithm, so to maintain a set of contacted node from time to time seems to be very simple. Could you please clarify ?– Jean-Baptiste Yunès
Nov 19 '18 at 8:34
Not clear why
a4 is not in the result list. Looks like a simple diffusion algorithm, so to maintain a set of contacted node from time to time seems to be very simple. Could you please clarify ?– Jean-Baptiste Yunès
Nov 19 '18 at 8:34
I have re-edit the question to make it clear.
– oleotiger
Nov 19 '18 at 10:48
I have re-edit the question to make it clear.
– oleotiger
Nov 19 '18 at 10:48
No that's not clear. Why at 3 a1 doesn't have the message? At 1, it already gave it to a2 so why is it available at 2??? Seems to be inconsistent
– Jean-Baptiste Yunès
Nov 19 '18 at 11:58
No that's not clear. Why at 3 a1 doesn't have the message? At 1, it already gave it to a2 so why is it available at 2??? Seems to be inconsistent
– Jean-Baptiste Yunès
Nov 19 '18 at 11:58
The node with message can decide when to transfer the message.
a1 can tranfer the message at time 1 or 2 or 3 or any time when there is a contact with another node. The purpose is to maximize the number of node which contacts with the message.– oleotiger
Nov 19 '18 at 15:16
The node with message can decide when to transfer the message.
a1 can tranfer the message at time 1 or 2 or 3 or any time when there is a contact with another node. The purpose is to maximize the number of node which contacts with the message.– oleotiger
Nov 19 '18 at 15:16
Ok then as I understand the problem is the longest path problem. That problem is known as NP-hard, which means that there is probably no efficient algorithm to solve it. It may exists some more efficient algorithms is your graph has some peculiar properties.
– Jean-Baptiste Yunès
Nov 19 '18 at 20:07
Ok then as I understand the problem is the longest path problem. That problem is known as NP-hard, which means that there is probably no efficient algorithm to solve it. It may exists some more efficient algorithms is your graph has some peculiar properties.
– Jean-Baptiste Yunès
Nov 19 '18 at 20:07
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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/3.0/"u003ecc by-sa 3.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%2fstackoverflow.com%2fquestions%2f53370227%2fhow-to-optimize-the-algorithm-to-find-the-max-depth-contact-series-in-a-time-var%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f53370227%2fhow-to-optimize-the-algorithm-to-find-the-max-depth-contact-series-in-a-time-var%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
Not clear why
a4is not in the result list. Looks like a simple diffusion algorithm, so to maintain a set of contacted node from time to time seems to be very simple. Could you please clarify ?– Jean-Baptiste Yunès
Nov 19 '18 at 8:34
I have re-edit the question to make it clear.
– oleotiger
Nov 19 '18 at 10:48
No that's not clear. Why at 3 a1 doesn't have the message? At 1, it already gave it to a2 so why is it available at 2??? Seems to be inconsistent
– Jean-Baptiste Yunès
Nov 19 '18 at 11:58
The node with message can decide when to transfer the message.
a1can tranfer the message at time1or2or3or any time when there is a contact with another node. The purpose is to maximize the number of node which contacts with the message.– oleotiger
Nov 19 '18 at 15:16
Ok then as I understand the problem is the longest path problem. That problem is known as NP-hard, which means that there is probably no efficient algorithm to solve it. It may exists some more efficient algorithms is your graph has some peculiar properties.
– Jean-Baptiste Yunès
Nov 19 '18 at 20:07