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

DOI10.1007/978-3-540-78773-0_17zbMATH Open1136.68459DBLPconf/latin/FominKLMT08OpenAlexW1565016281WikidataQ60488745 ScholiaQ60488745MaRDI QIDQ5458528FDOQ5458528

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

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

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

Mathematics Subject Classification ID

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

Cites Work

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

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)