Approximating maximum diameter-bounded subgraphs

DOI10.1007/978-3-642-12200-2_53MaRDI QIDQ3557054zbMATH OpenOpenAlexFDO

Authors Yuichi Asahiro, Kazuaki Samizo, Eiji Miyano

Publication date 27 April 2010

Published in LATIN 2010: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-12200-2_53

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• 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
• On approximating the maximum diameter ratio of graphs
• The approximation of maximum subgraph problems

Cited in

(20)

• On approximating the maximum diameter ratio of graphs
• Optimal approximation algorithms for maximum distance-bounded subgraph problems
• Parameterized computational complexity of finding small-diameter subgraphs
• An approximation algorithm for the maximum spectral subgraph problem
• Algorithms and complexity of \(s\)-club cluster vertex deletion
• The maximum degree \& diameter-bounded subgraph and its applications
• Approximating maximum diameter-bounded subgraph in unit disk graphs
• Distance-based clique relaxations in networks: s-clique and s-club
• On the 2-club polytope of graphs
• scientific article; zbMATH DE number 3857166 (Why is no real title available?)
• Optimal approximation algorithms for maximum distance-bounded subgraph problems
• Finding clubs in graph classes
• On inclusionwise maximal and maximum cardinality k-clubs in graphs
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• The approximation of maximum subgraph problems
• Finding large k-clubs in undirected graphs
• On Fault-Tolerant Low-Diameter Clusters in Graphs
• Approximating maximum diameter-bounded subgraph in unit disk graphs
• A dynamic programming algorithm for the maximum s-club problem on trees
• On the hardness of problems around s-clubs on split graphs

This page was built for publication: Approximating maximum diameter-bounded subgraphs

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