Content area

Abstract

Translate

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.

Details

1009240
Subject
Packing problem;
Graphs;
Graph theory
Identifier / keyword
Combinatorics
URL
http://arxiv.org/abs/2110.12783
Title
Packing Strong Subgraph in Digraphs
Author
Sun, Yuefang; Gutin, Gregory; Zhang, Xiaoyan
Publication title
arXiv.org; Ithaca
Publication year
2021
Publication date
Oct 25, 2021
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
2021-10-26
Milestone dates
2021-10-25 (Submission v1)
Publication history
 
 
   First posting date
26 Oct 2021
ProQuest document ID
2586237598
Document URL
https://www.proquest.com/working-papers/packing-strong-subgraph-digraphs/docview/2586237598/se-2?accountid=208611
Full text outside of ProQuest
http://arxiv.org/abs/2110.12783
Copyright
© 2021. 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
2021-10-27
Database
ProQuest One Academic