EUVIMEDEUVIMED entdecken
Crossref

Packing strong subgraph in digraphs

Yuefang Sun, Gregory Gutin, Xiaoyan Zhang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →