Packing strong subgraph in digraphs
Discrete Optimization · 2022-11 · 46 · 100745
DOI: 10.1016/j.disopt.2022.100745 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Optimization, 2022-11. Verfasst von Yuefang Sun und 2 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 31 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Natural Science Foundation of Zhejiang Province, Qinglan Project of Jiangsu Province of China.
Abstract (Originalsprache)
In this paper, we study two types of strong subgraph packing problems in digraphs, including internally disjoint strong subgraph packing problem and arc-disjoint strong subgraph packing problem. These problems can be viewed as generalizations of the famous Steiner tree packing problem and are closely related to the strong arc decomposition problem. We first prove the NP-completeness for the internally disjoint strong subgraph packing problem restricted to symmetric digraphs and Eulerian digraphs. Then we get inapproximability results for the arc-disjoint strong subgraph packing problem and the internally disjoint strong subgraph packing problem. Finally we study the arc-disjoint strong subgraph packing problem restricted to digraph compositions and obtain some algorithmic results by utilizing the structural properties.
Förderung
- National Natural Science Foundation of China
- Natural Science Foundation of Zhejiang Province
- Qinglan Project of Jiangsu Province of China
Zitieren
APA
Sun, Y., Gutin, G., & Zhang, X. (2022). Packing strong subgraph in digraphs. Discrete Optimization, 46, 100745. https://doi.org/10.1016/j.disopt.2022.100745
Vancouver
Sun Y, Gutin G, Zhang X. Packing strong subgraph in digraphs. Discrete Optimization. 2022;46:100745. doi:10.1016/j.disopt.2022.100745
BibTeX
@article{Sun2022,
author = {Sun, Yuefang and Gutin, Gregory and Zhang, Xiaoyan},
title = {Packing strong subgraph in digraphs},
journal = {Discrete Optimization},
year = {2022},
volume = {46},
pages = {100745},
doi = {10.1016/j.disopt.2022.100745}
}
EUVIMED