On the complexity of reconstructing H-free graphs from their Star Systems
From MaRDI portal
Publication:3174240
DOI10.1002/jgt.20544zbMath1230.05215WikidataQ60488573 ScholiaQ60488573MaRDI QIDQ3174240
Jan Kratochvíl, Fedor V. Fomin, Daniel Lokshtanov, Jan Arne Telle, Federico Mancini
Publication date: 12 October 2011
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.20544
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Reconstructing trees from digitally convex sets, Solving the canonical representation and star system problems for proper circular-arc graphs in logspace, Reconstructing Cactus Graphs from Shortest Path Information
Cites Work
- Le problème d'étoiles pour graphes est NP-complèt
- Complement reducible graphs
- Realizability and uniqueness in graphs
- Isomorphism Testing and Symmetry of Graphs
- Some NP-Complete Problems Similar to Graph Isomorphism
- Reconstructing a Graph from its Neighborhood Lists
- Neighborhood hypergraphs of bipartite graphs
- On the Complexity of Reconstructing H-free Graphs from Their Star Systems
