Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries

DOI10.1002/net.20404zbMath1223.05208OpenAlexW2045214814MaRDI QIDQ3087620

Peter Damaschke

Publication date: 16 August 2011

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20404

zbMATH Keywords

samplingdominating setdegree sequencesparse graphlearning by queries

Mathematics Subject Classification ID

Searching and sorting (68P10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Node sampling for protein complex estimation in bait-prey graphs

Cites Work

• Unnamed Item
• Learning a hidden graph using \(O(\log n)\)queries per edge
• Parameterized approximation of dominating set problems
• Finding a dense-core in jellyfish graphs
• Network Discovery and Verification with Distance Queries
• Parameterized Approximation Problems
• Discovery of Network Properties with All-Shortest-Paths Queries
• Approximate Discovery of Random Graphs
• Learning a Hidden Subgraph
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries