Optimal approximation algorithms for maximum distance-bounded subgraph problems
From MaRDI portal
Publication:1635712
DOI10.1007/s00453-017-0344-yzbMath1394.68435OpenAlexW2738793986MaRDI QIDQ1635712
Hirotaka Shimizu, Eiji Miyano, Kazuaki Samizo, Yuya Doi, Yuichi Asahiro
Publication date: 1 June 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-017-0344-y
Analysis of algorithms (68W40) Social networks; opinion dynamics (91D30) Approximation methods and heuristics in mathematical programming (90C59) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items
On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ Approximating maximum diameter-bounded subgraph in unit disk graphs ⋮ Covering a Graph with Clubs ⋮ Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments ⋮ Parsimonious formulations for low-diameter clusters ⋮ Top-\(k\) overlapping densest subgraphs: approximation algorithms and computational complexity ⋮ On the tractability of covering a graph with 2-clubs
Cites Work
- Unnamed Item
- Unnamed Item
- Finding clubs in graph classes
- Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
- On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
- Finding large \(k\)-clubs in undirected graphs
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- Radius, diameter, and minimum degree
- On approximating the maximum diameter ratio of graphs
- All pairs shortest paths for graphs with small integer length edges
- All pairs shortest distances for graphs with small integer length edges
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- An exact algorithm for the maximum \(k\)-club problem in an undirected graph
- Parameterized computational complexity of finding small-diameter subgraphs
- On structural parameterizations for the 2-club problem
- Novel approaches for analyzing biological networks
- Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems
- Approximating Maximum Diameter-Bounded Subgraphs
- A graph‐theoretic definition of a sociometric clique†
- A graph‐theoretic generalization of the clique concept
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- On provably best construction heuristics for hard combinatorial optimization problems
- Approximating Maximum Clique by Removing Subgraphs
- Reducibility among Combinatorial Problems
- Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
- Multiplying matrices faster than coppersmith-winograd
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
