On approximating the maximum diameter ratio of graphs

DOI10.1016/S0012-365X(01)00091-7zbMath0999.05056OpenAlexW2013563568MaRDI QIDQ1349101

Bojan Mohar, Jože Marinček

Publication date: 21 May 2002

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0012-365x(01)00091-7

zbMATH Keywords

approximation algorithmdiameterAPX-completelocal density

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (6)

Optimal approximation algorithms for maximum distance-bounded subgraph problems ⋮ Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems ⋮ On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs ⋮ A centrality notion for graphs based on Tukey depth ⋮ Parameterized computational complexity of finding small-diameter subgraphs ⋮ Distance-Based Clique Relaxations in Networks: s-Clique and s-Club

This page was built for publication: On approximating the maximum diameter ratio of graphs