Clustering Graphs of Bounded Treewidth to Minimize the Sum of Radius-Dependent Costs Article Swipe

PDF

Lukas Drexler , Jan Höckendorff , Joshua Könen , Kevin Schewior ·

YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2310.02130

We consider the following natural problem that generalizes min-sum-radii clustering: Given is $k\in\mathbb{N}$ as well as some metric space $(V,d)$ where $V=F\cup C$ for facilities $F$ and clients $C$. The goal is to find a clustering given by $k$ facility-radius pairs $(f_1,r_1),\dots,(f_k,r_k)\in F\times\mathbb{R}_{\geq 0}$ such that $C\subseteq B(f_1,r_1)\cup\dots\cup B(f_k,r_k)$ and $\sum_{i=1,\dots,k} g(r_i)$ is minimized for some increasing function $g:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$. Here, $B(x,r)$ is the radius-$r$ ball centered at $x$. For the case that $(V,d)$ is the shortest-path metric of some edge-weighted graph of bounded treewidth, we present a dynamic program that is tailored to this class of problems and achieves a polynomial running time, establishing that the problem is in $\mathsf{XP}$ with parameter treewidth.

Related Topics

Mathematical Analysis

Concepts

Treewidth Combinatorics Bounded function RADIUS Cluster analysis Mathematics Ball (mathematics) Graph Polynomial Discrete mathematics Pathwidth Geometry Mathematical analysis Computer science Statistics Line graph Computer security

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2310.02130
PDF: https://arxiv.org/pdf/2310.02130
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4387389523

All OpenAlex metadata

Raw OpenAlex JSON

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

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2310.02130

Digital Object Identifier
Title: Clustering Graphs of Bounded Treewidth to Minimize the Sum of Radius-Dependent Costs

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2023

Year of publication
Publication date: 2023-10-03

Full publication date if available
Authors: Lukas Drexler, Jan Höckendorff, Joshua Könen, Kevin Schewior

List of authors in order
Landing page: https://arxiv.org/abs/2310.02130

Publisher landing page
PDF URL: https://arxiv.org/pdf/2310.02130

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2310.02130

Direct OA link when available
Concepts: Treewidth, Combinatorics, Bounded function, RADIUS, Cluster analysis, Mathematics, Ball (mathematics), Graph, Polynomial, Discrete mathematics, Pathwidth, Geometry, Mathematical analysis, Computer science, Statistics, Line graph, Computer security

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

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4387389523
doi	https://doi.org/10.48550/arxiv.2310.02130
ids.doi	https://doi.org/10.48550/arxiv.2310.02130
ids.openalex	https://openalex.org/W4387389523
fwci
type	preprint
title	Clustering Graphs of Bounded Treewidth to Minimize the Sum of Radius-Dependent Costs
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11502
topics[0].field.id	https://openalex.org/fields/14
topics[0].field.display_name	Business, Management and Accounting
topics[0].score	0.9922000169754028
topics[0].domain.id	https://openalex.org/domains/2
topics[0].domain.display_name	Social Sciences
topics[0].subfield.id	https://openalex.org/subfields/1407
topics[0].subfield.display_name	Organizational Behavior and Human Resource Management
topics[0].display_name	Facility Location and Emergency Management
topics[1].id	https://openalex.org/T10374
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9807999730110168
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1703
topics[1].subfield.display_name	Computational Theory and Mathematics
topics[1].display_name	Advanced Graph Theory Research
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.9689000248908997
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/C132569581
concepts[0].level	5
concepts[0].score	0.8995219469070435
concepts[0].wikidata	https://www.wikidata.org/wiki/Q5067368
concepts[0].display_name	Treewidth
concepts[1].id	https://openalex.org/C114614502
concepts[1].level	1
concepts[1].score	0.8120731115341187
concepts[1].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[1].display_name	Combinatorics
concepts[2].id	https://openalex.org/C34388435
concepts[2].level	2
concepts[2].score	0.6755560040473938
concepts[2].wikidata	https://www.wikidata.org/wiki/Q2267362
concepts[2].display_name	Bounded function
concepts[3].id	https://openalex.org/C178635117
concepts[3].level	2
concepts[3].score	0.6143519878387451
concepts[3].wikidata	https://www.wikidata.org/wiki/Q747499
concepts[3].display_name	RADIUS
concepts[4].id	https://openalex.org/C73555534
concepts[4].level	2
concepts[4].score	0.5497699975967407
concepts[4].wikidata	https://www.wikidata.org/wiki/Q622825
concepts[4].display_name	Cluster analysis
concepts[5].id	https://openalex.org/C33923547
concepts[5].level	0
concepts[5].score	0.5208445191383362
concepts[5].wikidata	https://www.wikidata.org/wiki/Q395
concepts[5].display_name	Mathematics
concepts[6].id	https://openalex.org/C122041747
concepts[6].level	2
concepts[6].score	0.513195812702179
concepts[6].wikidata	https://www.wikidata.org/wiki/Q838611
concepts[6].display_name	Ball (mathematics)
concepts[7].id	https://openalex.org/C132525143
concepts[7].level	2
concepts[7].score	0.47853192687034607
concepts[7].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[7].display_name	Graph
concepts[8].id	https://openalex.org/C90119067
concepts[8].level	2
concepts[8].score	0.42653992772102356
concepts[8].wikidata	https://www.wikidata.org/wiki/Q43260
concepts[8].display_name	Polynomial
concepts[9].id	https://openalex.org/C118615104
concepts[9].level	1
concepts[9].score	0.3876500427722931
concepts[9].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[9].display_name	Discrete mathematics
concepts[10].id	https://openalex.org/C43517604
concepts[10].level	4
concepts[10].score	0.13692522048950195
concepts[10].wikidata	https://www.wikidata.org/wiki/Q7144893
concepts[10].display_name	Pathwidth
concepts[11].id	https://openalex.org/C2524010
concepts[11].level	1
concepts[11].score	0.11597761511802673
concepts[11].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[11].display_name	Geometry
concepts[12].id	https://openalex.org/C134306372
concepts[12].level	1
concepts[12].score	0.11596307158470154
concepts[12].wikidata	https://www.wikidata.org/wiki/Q7754
concepts[12].display_name	Mathematical analysis
concepts[13].id	https://openalex.org/C41008148
concepts[13].level	0
concepts[13].score	0.1106863021850586
concepts[13].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[13].display_name	Computer science
concepts[14].id	https://openalex.org/C105795698
concepts[14].level	1
concepts[14].score	0.0524330735206604
concepts[14].wikidata	https://www.wikidata.org/wiki/Q12483
concepts[14].display_name	Statistics
concepts[15].id	https://openalex.org/C203776342
concepts[15].level	3
concepts[15].score	0.0
concepts[15].wikidata	https://www.wikidata.org/wiki/Q1378376
concepts[15].display_name	Line graph
concepts[16].id	https://openalex.org/C38652104
concepts[16].level	1
concepts[16].score	0.0
concepts[16].wikidata	https://www.wikidata.org/wiki/Q3510521
concepts[16].display_name	Computer security
keywords[0].id	https://openalex.org/keywords/treewidth
keywords[0].score	0.8995219469070435
keywords[0].display_name	Treewidth
keywords[1].id	https://openalex.org/keywords/combinatorics
keywords[1].score	0.8120731115341187
keywords[1].display_name	Combinatorics
keywords[2].id	https://openalex.org/keywords/bounded-function
keywords[2].score	0.6755560040473938
keywords[2].display_name	Bounded function
keywords[3].id	https://openalex.org/keywords/radius
keywords[3].score	0.6143519878387451
keywords[3].display_name	RADIUS
keywords[4].id	https://openalex.org/keywords/cluster-analysis
keywords[4].score	0.5497699975967407
keywords[4].display_name	Cluster analysis
keywords[5].id	https://openalex.org/keywords/mathematics
keywords[5].score	0.5208445191383362
keywords[5].display_name	Mathematics
keywords[6].id	https://openalex.org/keywords/ball
keywords[6].score	0.513195812702179
keywords[6].display_name	Ball (mathematics)
keywords[7].id	https://openalex.org/keywords/graph
keywords[7].score	0.47853192687034607
keywords[7].display_name	Graph
keywords[8].id	https://openalex.org/keywords/polynomial
keywords[8].score	0.42653992772102356
keywords[8].display_name	Polynomial
keywords[9].id	https://openalex.org/keywords/discrete-mathematics
keywords[9].score	0.3876500427722931
keywords[9].display_name	Discrete mathematics
keywords[10].id	https://openalex.org/keywords/pathwidth
keywords[10].score	0.13692522048950195
keywords[10].display_name	Pathwidth
keywords[11].id	https://openalex.org/keywords/geometry
keywords[11].score	0.11597761511802673
keywords[11].display_name	Geometry
keywords[12].id	https://openalex.org/keywords/mathematical-analysis
keywords[12].score	0.11596307158470154
keywords[12].display_name	Mathematical analysis
keywords[13].id	https://openalex.org/keywords/computer-science
keywords[13].score	0.1106863021850586
keywords[13].display_name	Computer science
keywords[14].id	https://openalex.org/keywords/statistics
keywords[14].score	0.0524330735206604
keywords[14].display_name	Statistics
language	en
locations[0].id	pmh:oai:arXiv.org:2310.02130
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2310.02130
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2310.02130
locations[1].id	doi:10.48550/arxiv.2310.02130
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2310.02130
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5055626805
authorships[0].author.orcid	https://orcid.org/0000-0001-9395-6711
authorships[0].author.display_name	Lukas Drexler
authorships[0].author_position	first
authorships[0].raw_author_name	Drexler, Lukas
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5093013786
authorships[1].author.orcid
authorships[1].author.display_name	Jan Höckendorff
authorships[1].author_position	middle
authorships[1].raw_author_name	Höckendorff, Jan
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5093013787
authorships[2].author.orcid
authorships[2].author.display_name	Joshua Könen
authorships[2].author_position	middle
authorships[2].raw_author_name	Könen, Joshua
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5056422606
authorships[3].author.orcid	https://orcid.org/0000-0003-2236-0210
authorships[3].author.display_name	Kevin Schewior
authorships[3].author_position	last
authorships[3].raw_author_name	Schewior, Kevin
authorships[3].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://arxiv.org/pdf/2310.02130
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Clustering Graphs of Bounded Treewidth to Minimize the Sum of Radius-Dependent Costs
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11502
primary_topic.field.id	https://openalex.org/fields/14
primary_topic.field.display_name	Business, Management and Accounting
primary_topic.score	0.9922000169754028
primary_topic.domain.id	https://openalex.org/domains/2
primary_topic.domain.display_name	Social Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1407
primary_topic.subfield.display_name	Organizational Behavior and Human Resource Management
primary_topic.display_name	Facility Location and Emergency Management
related_works	https://openalex.org/W4299559467, https://openalex.org/W2949617446, https://openalex.org/W4294299870, https://openalex.org/W2748664888, https://openalex.org/W1582492864, https://openalex.org/W4295887958, https://openalex.org/W2745231626, https://openalex.org/W2964174631, https://openalex.org/W1810116456, https://openalex.org/W4300619607
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2310.02130
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2310.02130
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2310.02130
primary_location.id	pmh:oai:arXiv.org:2310.02130
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2310.02130
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2310.02130
publication_date	2023-10-03
publication_year	2023
referenced_works_count	0
abstract_inverted_index.a	34, 88, 101
abstract_inverted_index.C$	22
abstract_inverted_index.We	0
abstract_inverted_index.as	13, 15
abstract_inverted_index.at	68
abstract_inverted_index.by	37
abstract_inverted_index.in	110
abstract_inverted_index.is	11, 31, 52, 63, 75, 92, 109
abstract_inverted_index.of	79, 83, 97
abstract_inverted_index.to	32, 94
abstract_inverted_index.we	86
abstract_inverted_index.$F$	25
abstract_inverted_index.$k$	38
abstract_inverted_index.0}$	43
abstract_inverted_index.For	70
abstract_inverted_index.The	29
abstract_inverted_index.and	26, 49, 99
abstract_inverted_index.for	23, 54
abstract_inverted_index.the	2, 64, 71, 76, 107
abstract_inverted_index.$C$.	28
abstract_inverted_index.$x$.	69
abstract_inverted_index.0}$.	60
abstract_inverted_index.ball	66
abstract_inverted_index.case	72
abstract_inverted_index.find	33
abstract_inverted_index.goal	30
abstract_inverted_index.some	16, 55, 80
abstract_inverted_index.such	44
abstract_inverted_index.that	6, 45, 73, 91, 106
abstract_inverted_index.this	95
abstract_inverted_index.well	14
abstract_inverted_index.with	112
abstract_inverted_index.Given	10
abstract_inverted_index.Here,	61
abstract_inverted_index.class	96
abstract_inverted_index.given	36
abstract_inverted_index.graph	82
abstract_inverted_index.pairs	40
abstract_inverted_index.space	18
abstract_inverted_index.time,	104
abstract_inverted_index.where	20
abstract_inverted_index.metric	17, 78
abstract_inverted_index.$(V,d)$	19, 74
abstract_inverted_index.bounded	84
abstract_inverted_index.clients	27
abstract_inverted_index.dynamic	89
abstract_inverted_index.g(r_i)$	51
abstract_inverted_index.natural	4
abstract_inverted_index.present	87
abstract_inverted_index.problem	5, 108
abstract_inverted_index.program	90
abstract_inverted_index.running	103
abstract_inverted_index.$B(x,r)$	62
abstract_inverted_index.$V=F\cup	21
abstract_inverted_index.achieves	100
abstract_inverted_index.centered	67
abstract_inverted_index.consider	1
abstract_inverted_index.function	57
abstract_inverted_index.problems	98
abstract_inverted_index.tailored	93
abstract_inverted_index.following	3
abstract_inverted_index.minimized	53
abstract_inverted_index.parameter	113
abstract_inverted_index.clustering	35
abstract_inverted_index.facilities	24
abstract_inverted_index.increasing	56
abstract_inverted_index.polynomial	102
abstract_inverted_index.radius-$r$	65
abstract_inverted_index.treewidth,	85
abstract_inverted_index.treewidth.	114
abstract_inverted_index.$C\subseteq	46
abstract_inverted_index.B(f_k,r_k)$	48
abstract_inverted_index.clustering:	9
abstract_inverted_index.generalizes	7
abstract_inverted_index.establishing	105
abstract_inverted_index.$\mathsf{XP}$	111
abstract_inverted_index.edge-weighted	81
abstract_inverted_index.min-sum-radii	8
abstract_inverted_index.shortest-path	77
abstract_inverted_index.facility-radius	39
abstract_inverted_index.$k\in\mathbb{N}$	12
abstract_inverted_index.$\sum_{i=1,\dots,k}	50
abstract_inverted_index.$g:\mathbb{R}_{\geq	58
abstract_inverted_index.B(f_1,r_1)\cup\dots\cup	47
abstract_inverted_index.F\times\mathbb{R}_{\geq	42
abstract_inverted_index.$(f_1,r_1),\dots,(f_k,r_k)\in	41
abstract_inverted_index.0}\rightarrow\mathbb{R}_{\geq	59
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile