On the Complexity of Reconstructing H-free Graphs from Their Star Systems

DOI10.1007/978-3-540-78773-0_17MaRDI QIDQ5458528zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Fedor V. Fomin, Jan Kratochvíl, Daniel Lokshtanov, F. Mancini, Jan Arne Telle

Publication date 15 April 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-78773-0_17

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the complexity of reconstructing H-free graphs from their Star Systems
• Algorithms and Computation
• On Switching to H‐Free Graphs
• Induced star partition of graphs
• Forbidden induced subgraphs for star-free graphs

Cites work

• Complement reducible graphs
• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Isomorphism Testing and Symmetry of Graphs
• Le problème d'étoiles pour graphes est NP-complèt
• Neighborhood hypergraphs of bipartite graphs
• Realizability and uniqueness in graphs
• Reconstructing a Graph from its Neighborhood Lists
• Some NP-Complete Problems Similar to Graph Isomorphism
• Towards a dichotomy theorem for the counting constraint satisfaction problem

Cited in

(1)

• On the complexity of reconstructing H-free graphs from their Star Systems

This page was built for publication: On the Complexity of Reconstructing H-free Graphs from Their Star Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458528)