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

DOI10.1007/S10852-012-9182-8zbMATH Open1305.05149OpenAlexW2114448624MaRDI QIDQ2392540FDOQ2392540

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

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

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

zbMATH Keywords

network designdegree/diameter problemmeshbotnets

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• The maximum degree and diameter-bounded subgraph in the mesh
• Maximum subgraph problem for 3-regular Knödel graphs and its wirelength
• Title not available (Why is that?)
• Boundary graph classes for some maximum induced subgraph problems
• Degree diameter problem on honeycomb networks
• Distance-Based Clique Relaxations in Networks: s-Clique and s-Club
• A note on maximal common subgraphs of the Dirac's family of graphs
• 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)