On the Hardness and Approximation of the Densest $K$-Subgraph Problem in Parameterized Metric Graphs Article Swipe

View

Shih‐Chia Chang , Li-Hsuan Chen , Sun‐Yuan Hsieh , Ling-Ju Hung , Shih-Shun Kao , Ralf Klasing ·

YOU? · · 2022 · Open Access · · DOI: https://doi.org/10.2139/ssrn.4196893

Related Topics

Performance Indicator

Operations Management

Line Graph

Concepts

Parameterized complexity Metric (unit) Combinatorics Hardness of approximation Mathematics Induced subgraph isomorphism problem Discrete mathematics Approximation algorithm Graph Economics Operations management Voltage graph Line graph

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.2139/ssrn.4196893
OA Status: green
Cited By: 1
References: 38
Related Works: 10
OpenAlex ID: https://openalex.org/W4292826515

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4292826515

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.2139/ssrn.4196893

Digital Object Identifier
Title: On the Hardness and Approximation of the Densest $K$-Subgraph Problem in Parameterized Metric Graphs

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2022

Year of publication
Publication date: 2022-01-01

Full publication date if available
Authors: Shih‐Chia Chang, Li-Hsuan Chen, Sun‐Yuan Hsieh, Ling-Ju Hung, Shih-Shun Kao, Ralf Klasing

List of authors in order
Landing page: https://doi.org/10.2139/ssrn.4196893

Publisher landing page
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://doi.org/10.2139/ssrn.4196893

Direct OA link when available
Concepts: Parameterized complexity, Metric (unit), Combinatorics, Hardness of approximation, Mathematics, Induced subgraph isomorphism problem, Discrete mathematics, Approximation algorithm, Graph, Economics, Operations management, Voltage graph, Line graph

Top concepts (fields/topics) attached by OpenAlex
Cited by: 1

Total citation count in OpenAlex
Citations by year (recent): 2023: 1

Per-year citation counts (last 5 years)
References (count): 38

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4292826515
doi	https://doi.org/10.2139/ssrn.4196893
ids.doi	https://doi.org/10.2139/ssrn.4196893
ids.openalex	https://openalex.org/W4292826515
fwci	0.26334776
type	article
title	On the Hardness and Approximation of the Densest $K$-Subgraph Problem in Parameterized Metric Graphs
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10374
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9994999766349792
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Advanced Graph Theory Research
topics[1].id	https://openalex.org/T10996
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9993000030517578
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1704
topics[1].subfield.display_name	Computer Graphics and Computer-Aided Design
topics[1].display_name	Computational Geometry and Mesh Generation
topics[2].id	https://openalex.org/T10720
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9987999796867371
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1703
topics[2].subfield.display_name	Computational Theory and Mathematics
topics[2].display_name	Complexity and Algorithms in Graphs
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C165464430
concepts[0].level	2
concepts[0].score	0.9163140058517456
concepts[0].wikidata	https://www.wikidata.org/wiki/Q1570441
concepts[0].display_name	Parameterized complexity
concepts[1].id	https://openalex.org/C176217482
concepts[1].level	2
concepts[1].score	0.6641383767127991
concepts[1].wikidata	https://www.wikidata.org/wiki/Q860554
concepts[1].display_name	Metric (unit)
concepts[2].id	https://openalex.org/C114614502
concepts[2].level	1
concepts[2].score	0.5839841365814209
concepts[2].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[2].display_name	Combinatorics
concepts[3].id	https://openalex.org/C112955886
concepts[3].level	3
concepts[3].score	0.5792044997215271
concepts[3].wikidata	https://www.wikidata.org/wiki/Q5656275
concepts[3].display_name	Hardness of approximation
concepts[4].id	https://openalex.org/C33923547
concepts[4].level	0
concepts[4].score	0.5319661498069763
concepts[4].wikidata	https://www.wikidata.org/wiki/Q395
concepts[4].display_name	Mathematics
concepts[5].id	https://openalex.org/C191241153
concepts[5].level	5
concepts[5].score	0.4107832908630371
concepts[5].wikidata	https://www.wikidata.org/wiki/Q6027240
concepts[5].display_name	Induced subgraph isomorphism problem
concepts[6].id	https://openalex.org/C118615104
concepts[6].level	1
concepts[6].score	0.36736738681793213
concepts[6].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[6].display_name	Discrete mathematics
concepts[7].id	https://openalex.org/C148764684
concepts[7].level	2
concepts[7].score	0.3463420271873474
concepts[7].wikidata	https://www.wikidata.org/wiki/Q621751
concepts[7].display_name	Approximation algorithm
concepts[8].id	https://openalex.org/C132525143
concepts[8].level	2
concepts[8].score	0.19858789443969727
concepts[8].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[8].display_name	Graph
concepts[9].id	https://openalex.org/C162324750
concepts[9].level	0
concepts[9].score	0.11301326751708984
concepts[9].wikidata	https://www.wikidata.org/wiki/Q8134
concepts[9].display_name	Economics
concepts[10].id	https://openalex.org/C21547014
concepts[10].level	1
concepts[10].score	0.06242355704307556
concepts[10].wikidata	https://www.wikidata.org/wiki/Q1423657
concepts[10].display_name	Operations management
concepts[11].id	https://openalex.org/C22149727
concepts[11].level	4
concepts[11].score	0.0
concepts[11].wikidata	https://www.wikidata.org/wiki/Q7940747
concepts[11].display_name	Voltage graph
concepts[12].id	https://openalex.org/C203776342
concepts[12].level	3
concepts[12].score	0.0
concepts[12].wikidata	https://www.wikidata.org/wiki/Q1378376
concepts[12].display_name	Line graph
keywords[0].id	https://openalex.org/keywords/parameterized-complexity
keywords[0].score	0.9163140058517456
keywords[0].display_name	Parameterized complexity
keywords[1].id	https://openalex.org/keywords/metric
keywords[1].score	0.6641383767127991
keywords[1].display_name	Metric (unit)
keywords[2].id	https://openalex.org/keywords/combinatorics
keywords[2].score	0.5839841365814209
keywords[2].display_name	Combinatorics
keywords[3].id	https://openalex.org/keywords/hardness-of-approximation
keywords[3].score	0.5792044997215271
keywords[3].display_name	Hardness of approximation
keywords[4].id	https://openalex.org/keywords/mathematics
keywords[4].score	0.5319661498069763
keywords[4].display_name	Mathematics
keywords[5].id	https://openalex.org/keywords/induced-subgraph-isomorphism-problem
keywords[5].score	0.4107832908630371
keywords[5].display_name	Induced subgraph isomorphism problem
keywords[6].id	https://openalex.org/keywords/discrete-mathematics
keywords[6].score	0.36736738681793213
keywords[6].display_name	Discrete mathematics
keywords[7].id	https://openalex.org/keywords/approximation-algorithm
keywords[7].score	0.3463420271873474
keywords[7].display_name	Approximation algorithm
keywords[8].id	https://openalex.org/keywords/graph
keywords[8].score	0.19858789443969727
keywords[8].display_name	Graph
keywords[9].id	https://openalex.org/keywords/economics
keywords[9].score	0.11301326751708984
keywords[9].display_name	Economics
keywords[10].id	https://openalex.org/keywords/operations-management
keywords[10].score	0.06242355704307556
keywords[10].display_name	Operations management
language	en
locations[0].id	doi:10.2139/ssrn.4196893
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4210172589
locations[0].source.issn	1556-5068
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l	1556-5068
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	SSRN Electronic Journal
locations[0].source.host_organization	https://openalex.org/I1318003438
locations[0].source.host_organization_name	RELX Group (Netherlands)
locations[0].source.host_organization_lineage	https://openalex.org/I1318003438
locations[0].license
locations[0].pdf_url
locations[0].version	publishedVersion
locations[0].raw_type	journal-article
locations[0].license_id
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	SSRN Electronic Journal
locations[0].landing_page_url	https://doi.org/10.2139/ssrn.4196893
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5066205594
authorships[0].author.orcid
authorships[0].author.display_name	Shih‐Chia Chang
authorships[0].countries	TW
authorships[0].affiliations[0].institution_ids	https://openalex.org/I43566213
authorships[0].affiliations[0].raw_affiliation_string	National Taipei University of Business
authorships[0].institutions[0].id	https://openalex.org/I43566213
authorships[0].institutions[0].ror	https://ror.org/029hrv109
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I43566213
authorships[0].institutions[0].country_code	TW
authorships[0].institutions[0].display_name	National Taipei University of Business
authorships[0].author_position	first
authorships[0].raw_author_name	Shih-Chia Chang
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	National Taipei University of Business
authorships[1].author.id	https://openalex.org/A5055424928
authorships[1].author.orcid	https://orcid.org/0009-0007-6528-7064
authorships[1].author.display_name	Li-Hsuan Chen
authorships[1].author_position	middle
authorships[1].raw_author_name	Li-Hsuan Chen
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5103047340
authorships[2].author.orcid	https://orcid.org/0000-0003-4746-3179
authorships[2].author.display_name	Sun‐Yuan Hsieh
authorships[2].countries	TW
authorships[2].affiliations[0].institution_ids	https://openalex.org/I91807558
authorships[2].affiliations[0].raw_affiliation_string	National Cheng Kung University
authorships[2].institutions[0].id	https://openalex.org/I91807558
authorships[2].institutions[0].ror	https://ror.org/01b8kcc49
authorships[2].institutions[0].type	education
authorships[2].institutions[0].lineage	https://openalex.org/I91807558
authorships[2].institutions[0].country_code	TW
authorships[2].institutions[0].display_name	National Cheng Kung University
authorships[2].author_position	middle
authorships[2].raw_author_name	Sun-Yuan Hsieh
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	National Cheng Kung University
authorships[3].author.id	https://openalex.org/A5007511094
authorships[3].author.orcid	https://orcid.org/0000-0001-5659-5507
authorships[3].author.display_name	Ling-Ju Hung
authorships[3].countries	TW
authorships[3].affiliations[0].institution_ids	https://openalex.org/I43566213
authorships[3].affiliations[0].raw_affiliation_string	National Taipei University of Business
authorships[3].institutions[0].id	https://openalex.org/I43566213
authorships[3].institutions[0].ror	https://ror.org/029hrv109
authorships[3].institutions[0].type	education
authorships[3].institutions[0].lineage	https://openalex.org/I43566213
authorships[3].institutions[0].country_code	TW
authorships[3].institutions[0].display_name	National Taipei University of Business
authorships[3].author_position	middle
authorships[3].raw_author_name	Ling-Ju Hung
authorships[3].is_corresponding	False
authorships[3].raw_affiliation_strings	National Taipei University of Business
authorships[4].author.id	https://openalex.org/A5045206789
authorships[4].author.orcid	https://orcid.org/0000-0001-7695-3535
authorships[4].author.display_name	Shih-Shun Kao
authorships[4].author_position	middle
authorships[4].raw_author_name	Shih-Shun Kao
authorships[4].is_corresponding	False
authorships[5].author.id	https://openalex.org/A5112786437
authorships[5].author.orcid
authorships[5].author.display_name	Ralf Klasing
authorships[5].author_position	last
authorships[5].raw_author_name	Ralf Klasing
authorships[5].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://doi.org/10.2139/ssrn.4196893
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	On the Hardness and Approximation of the Densest $K$-Subgraph Problem in Parameterized Metric Graphs
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T10374
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9994999766349792
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Advanced Graph Theory Research
related_works	https://openalex.org/W1034070228, https://openalex.org/W2167355524, https://openalex.org/W2131810278, https://openalex.org/W2307719096, https://openalex.org/W1561811279, https://openalex.org/W2091368663, https://openalex.org/W3036402366, https://openalex.org/W2625725254, https://openalex.org/W2963411648, https://openalex.org/W2016001296
cited_by_count	1
counts_by_year[0].year	2023
counts_by_year[0].cited_by_count	1
locations_count	1
best_oa_location.id	doi:10.2139/ssrn.4196893
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4210172589
best_oa_location.source.issn	1556-5068
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l	1556-5068
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	SSRN Electronic Journal
best_oa_location.source.host_organization	https://openalex.org/I1318003438
best_oa_location.source.host_organization_name	RELX Group (Netherlands)
best_oa_location.source.host_organization_lineage	https://openalex.org/I1318003438
best_oa_location.license
best_oa_location.pdf_url
best_oa_location.version	publishedVersion
best_oa_location.raw_type	journal-article
best_oa_location.license_id
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	SSRN Electronic Journal
best_oa_location.landing_page_url	https://doi.org/10.2139/ssrn.4196893
primary_location.id	doi:10.2139/ssrn.4196893
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4210172589
primary_location.source.issn	1556-5068
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l	1556-5068
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	SSRN Electronic Journal
primary_location.source.host_organization	https://openalex.org/I1318003438
primary_location.source.host_organization_name	RELX Group (Netherlands)
primary_location.source.host_organization_lineage	https://openalex.org/I1318003438
primary_location.license
primary_location.pdf_url
primary_location.version	publishedVersion
primary_location.raw_type	journal-article
primary_location.license_id
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	SSRN Electronic Journal
primary_location.landing_page_url	https://doi.org/10.2139/ssrn.4196893
publication_date	2022-01-01
publication_year	2022
referenced_works	https://openalex.org/W2043097561, https://openalex.org/W2065641139, https://openalex.org/W2032279394, https://openalex.org/W2063494850, https://openalex.org/W1590159142, https://openalex.org/W2166944557, https://openalex.org/W1996641400, https://openalex.org/W2025698306, https://openalex.org/W1481223916, https://openalex.org/W2153849284, https://openalex.org/W1548489374, https://openalex.org/W4255030025, https://openalex.org/W2057017626, https://openalex.org/W2606334169, https://openalex.org/W1970964752, https://openalex.org/W1519679194, https://openalex.org/W2764084197, https://openalex.org/W2946735198, https://openalex.org/W2006278018, https://openalex.org/W2036836182, https://openalex.org/W1990605847, https://openalex.org/W1508890431, https://openalex.org/W2091602684, https://openalex.org/W6753639089, https://openalex.org/W2007362596, https://openalex.org/W2021294212, https://openalex.org/W1970871468, https://openalex.org/W1480102953, https://openalex.org/W2161076233, https://openalex.org/W1965734368, https://openalex.org/W2891069083, https://openalex.org/W4223950885, https://openalex.org/W2099459744, https://openalex.org/W2065766818, https://openalex.org/W2177686805, https://openalex.org/W4246219036, https://openalex.org/W2964670465, https://openalex.org/W2885465588
referenced_works_count	38
abstract_inverted_index
cited_by_percentile_year.max	94
cited_by_percentile_year.min	89
countries_distinct_count	1
institutions_distinct_count	6
citation_normalized_percentile.value	0.50667087
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False