Timeline for find the most similar topological ordering of a dag
Current License: CC BY-SA 4.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 17, 2021 at 3:11 | comment | added | 2016310588 | @MohammadAl-Turkistany the proposed question is actually a special case of the original problem. suppose there is only one empty TCAM entry at the bottom of TCAM, i.e., after the insertion of $r_u$, TCAM is completely occupied. We might as well put $r_u$ into the only empty TCAM entry and the corresponding TCAM layout is $L$. Since such rule placement may violate the topological order, we need to relocate some rules. In this case, it easy to see that , the rule (including $r_u$) topological order which is the most similar to $L$ corresponds to the minimum TCAM operations. | |
| Aug 17, 2021 at 2:52 | comment | added | 2016310588 | @Mohammad Al-Turkistany ``TCAM'', the hardware for rule table lookup, requires rules to be placed in their topological order. When we want to insert a new rule $r$ to the TCAM, some rule has to be relocated. Since the TCAM only provides two types of equal-cost operations: write and nullify, we want to calculate the minimum number of TCAM operations to insert the new rule $r_u$. | |
| Aug 16, 2021 at 21:55 | comment | added | Mohammad Al-Turkistany | What is the motivation for your question? | |
| Mar 26, 2021 at 4:22 | history | edited | Mohammad Al-Turkistany |
edited tags
|
|
| Sep 2, 2020 at 14:06 | vote | accept | 2016310588 | ||
| Aug 13, 2020 at 1:23 | vote | accept | 2016310588 | ||
| Sep 2, 2020 at 14:05 | |||||
| Aug 13, 2020 at 1:17 | vote | accept | 2016310588 | ||
| Aug 13, 2020 at 1:23 | |||||
| Aug 13, 2020 at 1:15 | vote | accept | 2016310588 | ||
| Aug 13, 2020 at 1:15 | |||||
| S Aug 6, 2020 at 8:00 | history | bounty ended | CommunityBot | ||
| S Aug 6, 2020 at 8:00 | history | notice removed | CommunityBot | ||
| Aug 1, 2020 at 22:11 | answer | added | Vinicius dos Santos | timeline score: 0 | |
| Jul 30, 2020 at 10:32 | answer | added | domotorp | timeline score: 2 | |
| Jul 30, 2020 at 3:38 | history | edited | 2016310588 | CC BY-SA 4.0 |
deleted 129 characters in body
|
| Jul 30, 2020 at 1:37 | comment | added | 2016310588 | @MikhailRudoy By the way, our purpose is not to find the least number of label exchanges (or, swaps) but to find the least number of vertices whose label has been changed. | |
| Jul 30, 2020 at 1:17 | comment | added | 2016310588 | @MikhailRudoy Yes, your understanding is correct. | |
| Jul 29, 2020 at 16:11 | comment | added | Mikhail Rudoy | So just to make sure I have the idea right, here's the problem I think you are asking about: you are given a DAG with $n$ vertices labeled $1$ through $n$; the goal is to rearrange the labels such that under the new labeling scheme, the order implied by the new labels is a topological sort of the DAG and such that the number of vertices keeping their original labels is maximized. Is that right? Thanks! | |
| Jul 29, 2020 at 15:34 | comment | added | 2016310588 | @Mikhail Rudoy thanks for your attention! I am sorry for the ambiguity. (a) is the exact metric. | |
| Jul 29, 2020 at 13:10 | comment | added | Mikhail Rudoy | I'm not entirely sure which metric you're using for "most similar". When evaluating a potential ordering $O$, do you (a) try to minimize the number of positions where $O$ is different from $L$, (b) try to minimize the number of swaps needed to get from $O$ to $L$, or (c) something else? Different parts of your question point to either (a) or (b), but they are different metrics, so the answer can depend on which you meant. | |
| Jul 29, 2020 at 9:00 | history | tweeted | twitter.com/StackCSTheory/status/1288398880569270273 | ||
| S Jul 29, 2020 at 6:14 | history | bounty started | 2016310588 | ||
| S Jul 29, 2020 at 6:14 | history | notice added | 2016310588 | Authoritative reference needed | |
| Jul 28, 2020 at 1:12 | comment | added | 2016310588 | Thanks a lot for your help ! I will study these two issues carefully to see if there is a connection. | |
| Jul 27, 2020 at 14:01 | comment | added | Neal Young | Here are two other posts about NP-hard problems that ask for a topological ordering of a DAG that is optimal by some measure: cstheory.stackexchange.com/questions/31975/…, cstheory.stackexchange.com/questions/36230/…. Maybe these will give some ideas for coming up with an NP-hardness proof. | |
| Jul 27, 2020 at 4:23 | history | asked | 2016310588 | CC BY-SA 4.0 |