On approximating the maximum diameter ratio of graphs

DOI10.1016/S0012-365X(01)00091-7MaRDI QIDQ1349101zbMATH OpenOpenAlexFDO

Authors Jože Marinček, Bojan Mohar

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 algorithmdiameterlocal densityAPX-complete

Mathematics Subject Classification ID

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

Recommendations

• Approximating maximum diameter-bounded subgraphs
• Approximating maximum diameter-bounded subgraph in unit disk graphs
• Optimal approximation algorithms for maximum distance-bounded subgraph problems
• Optimal approximation algorithms for maximum distance-bounded subgraph problems
• scientific article; zbMATH DE number 3857166

Cited in

(10)

• Parameterized computational complexity of finding small-diameter subgraphs
• On Approximating the d-Girth of a Graph
• Optimal approximation algorithms for maximum distance-bounded subgraph problems
• Optimal approximation algorithms for maximum distance-bounded subgraph problems
• A centrality notion for graphs based on Tukey depth
• Approximating maximum diameter-bounded subgraphs
• Distance-based clique relaxations in networks: \(s\)-clique and \(s\)-club
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
• scientific article; zbMATH DE number 3857166 (Why is no real title available?)

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

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