Content area

Abstract

Translate

Graph packing problem is one of the central problems in graph theory and combinatorial optimization. The famous Steiner tree packing problem in undirected graphs has become an well-established area. It is natural to extend this problem to digraphs. In this survey we overview known results on several Steiner type packing problems in digraphs. The paper is divided into six sections: introduction, directed Steiner tree packing problem, directed Steiner path packing problem, strong subgraph packing problem, strong arc decomposition problem, directed Steiner cycle packing problem. This survey also contains some conjectures and open problems for further study.

Details

1009240
Subject
Apexes;
Graph theory
Identifier / keyword
Combinatorics
URL
http://arxiv.org/abs/2206.12092
Title
Steiner Type Packing Problems in Digraphs: A Survey
Author
Sun, Yuefang
Publication title
arXiv.org; Ithaca
Publication year
2022
Publication date
Dec 17, 2022
Section
Mathematics
Publisher
Cornell University Library, arXiv.org
Source
arXiv.org
Place of publication
Ithaca
Country of publication
United States
University/institution
Cornell University Library arXiv.org
Publication subject
Biology, Statistics, Physics, Mathematics, Engineering--Electrical Engineering, Computers--Computer Engineering, Business And Economics--Banking And Finance
e-ISSN
2331-8422
Source type
Working Paper
Language of publication
English
Document type
Working Paper
Publication history
 
 
Online publication date
2022-12-20
Milestone dates
2022-06-24 (Submission v1); 2022-08-20 (Submission v2); 2022-10-16 (Submission v3); 2022-12-17 (Submission v4)
Publication history
 
 
   First posting date
20 Dec 2022
ProQuest document ID
2681280491
Document URL
https://www.proquest.com/working-papers/steiner-type-packing-problems-digraphs-survey/docview/2681280491/se-2?accountid=208611
Full text outside of ProQuest
http://arxiv.org/abs/2206.12092
Copyright
© 2022. This work is published under http://arxiv.org/licenses/nonexclusive-distrib/1.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.
Last updated
2022-12-21
Database
ProQuest One Academic