The maximum degree \& diameter-bounded subgraph and its applications

DOI10.1007/S10852-012-9182-8MaRDI QIDQ2392540zbMATH OpenOpenAlexFDO

Authors Anthony H. Dekker, Hebert Pérez-Rosés, Guillermo Pineda-Villavicencio, P. Watters

Publication date 1 August 2013

Published in JMMA. Journal of Mathematical Modelling and Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10852-012-9182-8

zbMATH Keywords

botnetsdegree/diameter problemmeshnetwork design

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Applications of graph theory (05C90) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The maximum degree and diameter-bounded subgraph in the mesh
• MaxDDBS problem on butterfly networks
• scientific article; zbMATH DE number 1263586
• scientific article; zbMATH DE number 4087453
• On the approximability of some degree-constrained subgraph problems

Cites work

• A family of graphs and the degree/diameter problem
• Approximating maximum diameter-bounded subgraphs
• Approximating the degree-bounded minimum diameter spanning tree problem
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• Emergence of Scaling in Random Networks
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• Lipschitz class, narrow class, and counting lattice points
• The NP-completeness column: An ongoing guide
• Variation of the number of lattice points in large balls

Cited in

(10)

• Relaxation and matrix randomized rounding for the maximum spectral subgraph problem
• Boundary graph classes for some maximum induced subgraph problems
• Distance-based clique relaxations in networks: s-clique and s-club
• The maximum degree and diameter-bounded subgraph in the mesh
• MaxDDBS problem on butterfly networks
• Degree diameter problem on honeycomb networks
• scientific article; zbMATH DE number 1833409 (Why is no real title available?)
• A note on maximal common subgraphs of the Dirac's family of graphs
• Maximum subgraph problem for 3-regular Knödel graphs and its wirelength
• Optimal graphs in the enhanced mesh networks

This page was built for publication: The maximum degree \& diameter-bounded subgraph and its applications

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