Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms BAWCMJQGVA
| URI | m2://res/BAWCMJQGVA |
|---|---|
| Kind | preprint |
| Creators | Julian D. Allagan, Kevin Pereyra, William A. Massey |
| Date | 2026-09-25 |
| MSC | 05-XX, 49-XX, 90-XX, 93-XX |
| Subjects | arxiv math.CO, arxiv math.OC |
| Scope | in |
Expressions
e1: version, preprint
| Language | en |
|---|---|
| Date | 2026-09-25 |
| Ids | arXiv 2609.31535, zbl_id 903183718 |
Items in this resource
The mentions of the inventory that name this resource. Each name links to the card of its inventory row.
| Item | Kind | Where | Source |
|---|---|---|---|
| Exact mixed-integer linear formulation | statement | proposition 4.4 | arxiv |
| Stars | statement | corollary 6.7 | arxiv |
| Continuation cost | statement | lemma 6.1 | arxiv |
| Admissible gap and tail lengths | statement | lemma 5.5 | arxiv |
| \textsc{Discounted Hitting Domination | problem | problem 4.5 | arxiv |
| A four-agent verification chain | example | example 2.8 | arxiv |
| Equilibrium and geometric convergence | statement | theorem 2.2 | arxiv |
| Exact polynomial-time algorithm on spiders | statement | theorem 6.5 | arxiv |
| Recovery of ordinary domination | statement | corollary 3.5 | arxiv |
| Transfer sequences | statement | lemma 5.1 | arxiv |
| Exact one-source criterion | statement | corollary 6.6 | arxiv |
| Complexity at fixed parameters | statement | theorem 4.6 | arxiv |
| Discounted hitting potential | statement | theorem 2.3 | arxiv |
| Reflecting tail | statement | lemma 5.4 | arxiv |
| Greedy aggregate-support guarantee | statement | corollary 4.2 | arxiv |
| Exact spider formula | statement | theorem 6.3 | arxiv |
| Complete graphs | statement | proposition 7.1 | arxiv |
| Discounted hitting domination | definition | definition 2.5 | arxiv |
| Pinned discounted dynamics | definition | definition 2.1 | arxiv |
| Distance-domination sandwich | statement | corollary 3.3 | arxiv |
| Distance bounds | statement | proposition 3.1 | arxiv |
| Cost with a source at the center | statement | proposition 6.2 | arxiv |
| Submodular-cover formulation | statement | proposition 4.3 | arxiv |
| The branching vertex can be absent from every optimum | example | example 6.8 | arxiv |
| Equal distance, unequal support | example | example 3.6 | arxiv |
| Two-boundary segment | statement | lemma 5.3 | arxiv |
| Exact recovery of distance domination | statement | theorem 3.4 | arxiv |
| Submodularity | statement | theorem 4.1 | arxiv |
Catalogue records
- arxiv: 2609.31535 (work)
- arxiv_text: 2609.31535 (work)
- zbmath_search: 903183718 (work)