Timeline for Finding the subgraph with the largest diameter
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 26, 2017 at 21:32 | vote | accept | koalo | ||
| Nov 26, 2017 at 21:31 | answer | added | Fedor Petrov | timeline score: 6 | |
| Nov 26, 2017 at 21:07 | comment | added | koalo | @FlorianLehner I agree and thanks for the pointers to the publications! | |
| Nov 26, 2017 at 21:04 | comment | added | koalo | @FedorPetrov That seems to be the case, thanks! Would you convert your comment into an answer, so I can accept it? | |
| Nov 26, 2017 at 20:53 | comment | added | Florian Lehner | If I'm not mistaken, finding the induced subgraph with the largest diameter also gives the length of the longest induced path which (unless P = NP) can't even be efficiently approximated, see P. Berman, G. Schnitger, On the complexity of approximating the independent set problem, Information and Computation 96 (1), 1992. | |
| Nov 26, 2017 at 20:47 | comment | added | Fedor Petrov | Equivalently, we want to find the longest induced path. According to Wikipedia, it is NP-hard to find it. en.m.wikipedia.org/wiki/Induced_path | |
| Nov 26, 2017 at 20:40 | history | edited | koalo | CC BY-SA 3.0 |
minor clarification
|
| Nov 26, 2017 at 19:09 | review | First posts | |||
| Nov 26, 2017 at 20:54 | |||||
| Nov 26, 2017 at 19:08 | history | asked | koalo | CC BY-SA 3.0 |