Optimal approximation algorithms for maximum distance-bounded subgraph problems
type: Item
instance of: scholarly article
title: Optimal approximation algorithms for maximum distance-bounded subgraph problems
zbMATH Open document ID: 1394.68435
author: Yuichi Asahiro
author: Yuya Doi
author: Eiji Miyano
author: Kazuaki Samizo
author: Hirotaka Shimizu
published in: Algorithmica
publication date: 2018-06-01T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 91D30
zbMATH DE Number: 6879865
zbMATH Keywords: \(d\)-clique
zbMATH Keywords: \(d\)-club
zbMATH Keywords: maximum distance-bounded subgraph problems
zbMATH Keywords: (in)approximability
MaRDI profile type: Publication
full work available at URL: s00453-017-0344-y
OpenAlex ID: W2738793986
cites work: Q3044359
cites work: A graph‐theoretic definition of a sociometric clique†
cites work: Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems
cites work: Approximating Maximum Diameter-Bounded Subgraphs
cites work: Novel approaches for analyzing biological networks
cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results
cites work: An exact algorithm for the maximum \(k\)-club problem in an undirected graph
cites work: Finding large \(k\)-clubs in undirected graphs
cites work: Radius, diameter, and minimum degree
cites work: Approximating Maximum Clique by Removing Subgraphs
cites work: All pairs shortest distances for graphs with small integer length edges
cites work: All pairs shortest paths for graphs with small integer length edges
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: Finding clubs in graph classes
cites work: Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
cites work: On structural parameterizations for the 2-club problem
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: On provably best construction heuristics for hard combinatorial optimization problems
cites work: Reducibility among Combinatorial Problems
cites work: On approximating the maximum diameter ratio of graphs
cites work: On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
cites work: Parameterized computational complexity of finding small-diameter subgraphs
cites work: On the all-pairs-shortest-path problem in unweighted undirected graphs.
cites work: A graph‐theoretic generalization of the clique concept
cites work: Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
cites work: Multiplying matrices faster than coppersmith-winograd
cites work: Q3002782
DOI: 10.1007/S00453-017-0344-Y
Recommended article: Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems
Recommended article: The approximation of maximum subgraph problems
Recommended article: Approximating Maximum Diameter-Bounded Subgraphs
Recommended article: An approximation algorithm for the maximum spectral subgraph problem
Recommended article: Q4778538
Recommended article: Approximate Max \(k\)-Cut with subgraph guarantee
Recommended article: On the approximability of the maximum common subgraph problem
Recommended article: A deterministic approximation algorithm for the densest \(k\)-subgraph problem
Recommended article: Exact approaches for the minimum subgraph diameter problem
Recommended article: Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems
description: scientific article; zbMATH DE number 6879865