On the computational complexity of graph reconstruction

DOI10.1007/978-3-031-92932-8_10MaRDI QIDQ6902201zbMATH OpenFDO

Authors Cristina Bazgan, Morgan Chopin, André Nichterlein, Camille Richer

Publication date 11 November 2025

Full work available at URL https://doi.org/10.1007/978-3-031-92932-8_10

zbMATH Keywords

fixed-parameter-tractabilitygraph recoverylinear threshold modelnetwork inference

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Constant thresholds can make target set selection tractable
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• Fundamentals of parameterized complexity
• Graph reconstruction and verification
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• Local majorities, coalitions and monopolies in graphs: A review
• Networks, crowds and markets. Reasoning about a highly connected world.
• Networks. An introduction.
• On the approximability of influence in social networks
• Parameterized inapproximability of target set selection and generalizations
• Target Set Selection in Dense Graph Classes
• Treewidth governs the complexity of target set selection

This page was built for publication: On the computational complexity of graph reconstruction

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