Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2309.12853 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917918062673920 |
|---|---|
| author | Davis, Mya Hammarsten, Carl Menon, Siddarth Pasaylo, Maria Sheridan, Dane |
| author_facet | Davis, Mya Hammarsten, Carl Menon, Siddarth Pasaylo, Maria Sheridan, Dane |
| contents | Given a graph $G$ rooted at a vertex $r$ and weight functions, $γ, τ: E(G) \rightarrow \mathbb{R}$, the generalized cable-trench problem (CTP) is to find a single spanning tree that simultaneously minimizes the sum of the total edge cost with respect to $τ$ and the single-source shortest paths cost with respect to $γ$. Although this problem is provably $NP$-complete in the general case, we examine certain tractable instances involving various graph constructions of trees and cycles, along with quantities associated to edges and vertices that arise out of these constructions. We show that given a graph in which all cycles are edge disjoint, there exists a fast method to determine a cable-trench solution. Further, we examine properties of graphs which contribute to the general intractability of the CTP and present some open questions in this direction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_12853 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Classifying Tractable Instances of the Generalized Cable-Trench Problem Davis, Mya Hammarsten, Carl Menon, Siddarth Pasaylo, Maria Sheridan, Dane Combinatorics Given a graph $G$ rooted at a vertex $r$ and weight functions, $γ, τ: E(G) \rightarrow \mathbb{R}$, the generalized cable-trench problem (CTP) is to find a single spanning tree that simultaneously minimizes the sum of the total edge cost with respect to $τ$ and the single-source shortest paths cost with respect to $γ$. Although this problem is provably $NP$-complete in the general case, we examine certain tractable instances involving various graph constructions of trees and cycles, along with quantities associated to edges and vertices that arise out of these constructions. We show that given a graph in which all cycles are edge disjoint, there exists a fast method to determine a cable-trench solution. Further, we examine properties of graphs which contribute to the general intractability of the CTP and present some open questions in this direction. |
| title | Classifying Tractable Instances of the Generalized Cable-Trench Problem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2309.12853 |