"RIV/00216208:11320/11:10103380" . . "11320" . "US - Spojen\u00E9 st\u00E1ty americk\u00E9" . "http://dx.doi.org/10.1002/jgt.20544" . "Fomin, Fedor V." . "218182" . . . "000294818900003" . . "On the Complexity of Reconstructing H-Free Graphs from Their Star Systems"@en . . . "P(1M0545), Z(MSM0021620838)" . "Telle, Jan Arne" . "We study the computational complexity of the H-free Star System problem. We prove that when H is a path or a cycle on at most four vertices the problem is polynomial time solvable. In complement to this result, we show that if H belongs to a certain large class of graphs the H-free Star System problem is NP-complete. In particular, the problem is NP-complete when H is either a cycle or a path on at least five vertices. This yields a complete dichotomy for paths and cycles."@en . . "2" . "On the Complexity of Reconstructing H-Free Graphs from Their Star Systems" . "[FD64CCB69A4C]" . . "1"^^ . "68" . "We study the computational complexity of the H-free Star System problem. We prove that when H is a path or a cycle on at most four vertices the problem is polynomial time solvable. In complement to this result, we show that if H belongs to a certain large class of graphs the H-free Star System problem is NP-complete. In particular, the problem is NP-complete when H is either a cycle or a path on at least five vertices. This yields a complete dichotomy for paths and cycles." . . "Kratochv\u00EDl, Jan" . "0364-9024" . . . . "RIV/00216208:11320/11:10103380!RIV12-MSM-11320___" . . "10.1002/jgt.20544" . "5"^^ . "On the Complexity of Reconstructing H-Free Graphs from Their Star Systems"@en . "Lokshtanov, Daniel" . . "Mancini, Federico" . "On the Complexity of Reconstructing H-Free Graphs from Their Star Systems" . "Graph; Reconstruction; Complexity"@en . . "Journal of Graph Theory" . . . . "12"^^ .