Threshold dominating cliques in random graphs and interval routing

DOI10.1016/j.jda.2008.11.002zbMath1176.90604OpenAlexW2071645752MaRDI QIDQ1044044

Yong Gao

Publication date: 10 December 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.11.002

zbMATH Keywords

random graphsinterval routing schemesthreshold dominating cliques

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Stochastic network models in operations research (90B15) Traffic problems in operations research (90B20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The complexity of connected dominating sets and total dominating sets with specified induced subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Threshold dominating sets and an improved characterization of \(W[2\)]
• A survey on interval routing
• An exact algorithm for the minimum dominating clique problem
• The Compactness of Interval Routing for Almost All Graphs
• Random Instances of W[2-Complete Problems: Thresholds, Complexity, and Algorithms]
• The Complexity of Interval Routing on Random Graphs
• Algorithms and Computation