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 algorithmAPX-completediameterlocal density

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) 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)

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

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)