In the present work we study the problem of reconstructing a graph from its closed neighbourhood list. We will explore this problem, formulated by V. Sós, from the point of view of the fixed parameter complexity. We study the graph reconstruction problem in a more general setting, when the reconstructed graph is required to belong to some special graph class. In the present work we prove that this general problem lies in the complexity class FPT, when parametrized by the treewidth and maximum degree of the reconstructed graph, or by the number of certain special induced subgraphs if the reconstructed graph is 2-degenerate. Also, we prove that the graph reconstruction problem lies in the complexity class XP when parametrized by the vertex cover number. Finally, we prove mutual independence of the results
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:379578 |
| Date | January 2011 |
| Creators | Melka, Jakub |
| Contributors | Kratochvíl, Jan, Fiala, Jiří |
| Source Sets | Czech ETDs |
| Language | Czech |
| Detected Language | English |
| Type | info:eu-repo/semantics/masterThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0022 seconds