Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems

DOI10.1007/978-3-319-26626-8_43zbMath1474.68206OpenAlexW2258251439MaRDI QIDQ3467873

Yuichi Asahiro, Hirotaka Shimizu, Yuya Doi, Eiji Miyano

Publication date: 5 February 2016

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-26626-8_43

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (1)

Optimal approximation algorithms for maximum distance-bounded subgraph problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding clubs in graph classes
• On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
• Finding large \(k\)-clubs in undirected graphs
• Trapezoid graphs and generalizations, geometry and algorithms
• Radius, diameter, and minimum degree
• On approximating the maximum diameter ratio of graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Parameterized computational complexity of finding small-diameter subgraphs
• Optimizing weakly triangulated graphs
• On powers of \(m\)-trapezoid graphs
• Approximating Maximum Diameter-Bounded Subgraphs
• A graph‐theoretic definition of a sociometric clique†
• Graph Classes: A Survey
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Generalized Powers of Graphs and Their Algorithmic Use

This page was built for publication: Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems