On the complexity of list H-packing for sparse graph classes

• Item type: SIG Technical Reports(1)
• 公開日: 2024-01-13
• タイトル: On the complexity of list H-packing for sparse graph classes
• タイトル / 言語: en
• タイトル: On the complexity of list H-packing for sparse graph classes
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Graduate School of Informatics, Nagoya University／JSPS
• 著者所属: Department of Informatics, Kyushu University
• 著者所属: Graduate School of Information Science and Technology, Hokkaido University
• 著者所属: Graduate School of Informatics, Nagoya University
• 著者所属: Graduate School of Information Sciences, Tohoku University
• 著者所属: Graduate School of Information Sciences, Tohoku University
• 著者所属: Graduate School of Information Sciences, Tohoku University
• 著者所属: Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Nagoya University / JSPS
• 著者所属(英): en
• 著者所属(英): Department of Informatics, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Hokkaido University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Nagoya University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者名: Tatsuya, Gima; Tesshu, Hanaka; Yasuaki, Kobayashi; Yota, Otachi; Tomohito, Shirai; Akira, Suzuki; Yuma, Tamura; Xiao, Zhou
• 著者名(英): Tatsuya, Gima; Tesshu, Hanaka; Yasuaki, Kobayashi; Yota, Otachi; Tomohito, Shirai; Akira, Suzuki; Yuma, Tamura; Xiao, Zhou
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: The problem of packing as many subgraphs isomorphic to H ∈ H as possible in a graph for a class H of graphs is well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for H that contains at least three vertices and at least three edges, respectively. In this paper, we consider “list variants” of these problems: Given a graph G, an integer k, and a collection LH of subgraphs of G isomorphic to some H ∈ H, the goal is to compute k subgraphs in LH that are pairwise vertex- or edge-disjoint. We show several positive and negative results, focusing on classes of sparse graphs, such as bounded-degree graphs, planar graphs, and bounded-treewidth graphs.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The problem of packing as many subgraphs isomorphic to H ∈ H as possible in a graph for a class H of graphs is well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for H that contains at least three vertices and at least three edges, respectively. In this paper, we consider “list variants” of these problems: Given a graph G, an integer k, and a collection LH of subgraphs of G isomorphic to some H ∈ H, the goal is to compute k subgraphs in LH that are pairwise vertex- or edge-disjoint. We show several positive and negative results, focusing on classes of sparse graphs, such as bounded-degree graphs, planar graphs, and bounded-treewidth graphs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2024-AL-196, 号 5, p. 1-7, 発行日 2024-01-13
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会