Hardness of bounding influence via graph modification

DOI10.1007/978-3-031-23101-8_9MaRDI QIDQ6169517zbMATH OpenOpenAlexFDO

Authors Robert D. Barish, Tetsuo Shibuya

Publication date 14 August 2023

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

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

zbMATH Keywords

approximation hardnessbetweenness centralitycloseness centralitydegree centralityedge augmentationedge deletioneigenvector centralityharmonic centralityKatz centralityNP-hardnessPageRank centralityvertex deletion

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The parameterized complexity of centrality improvement in networks
• On making a distinguished vertex minimum degree by vertex deletion
• On making a distinguished vertex of minimum degree by vertex deletion
• scientific article; zbMATH DE number 7075920

Cites work

• A new status index derived from sociometric analysis
• Betweenness centrality in some classes of graphs
• Ergodic Control and Polyhedral Approaches to PageRank Optimization
• Graph theory
• Harmony in the small-world
• Improving the betweenness centrality of a node by adding links
• Maximizing PageRank via outlinks
• Node-and edge-deletion NP-complete problems
• On maximum induced matchings in bipartite graphs
• On the approximability of the link building problem
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
• On the maximum betweenness improvement problem
• PageRank optimization by edge selection
• PageRank optimization in polynomial time by stochastic shortest path reformulation
• Reducibility among combinatorial problems
• The centrality index of a graph
• The Effect of New Links on Google Pagerank
• The Many Proofs and Applications of Perron's Theorem
• The node-deletion problem for hereditary properties is NP-complete
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• The Planar Hamiltonian Circuit Problem is NP-Complete

This page was built for publication: Hardness of bounding influence via graph modification

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