Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems
From MaRDI portal
Publication:3467873
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
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
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
