On the complexity of some edge-partition problems for graphs

被引：7
|
作者：
Lonc, Z
机构：
[1] Institute of Mathematics, Warsaw University of Technology
来源：
DISCRETE APPLIED MATHEMATICS | 1996年 / 70卷 / 02期
关键词：
D O I：
10.1016/0166-218X(95)00107-3
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
For a family g of stars, a g-decomposition of a graph H is a partition of the edge set of H into subgraphs isomorphic to members of V. We show that, if g contains neither the 1-edge nor the 2-edge star, it is NP-complete to decide whether a bipartite graph admits a g-decomposition. This result enables us to strengthen a result of Hell and Kirkpatrick on partitioning the vertex set of a graph into complete graphs of certain orders. If g contains a 2-edge star, we obtain a good characterization of graphs (not necessarily bipartite) that admit g-decompositions. This characterization yields a linear time algorithm for constructing such a decomposition, if it exists.
引用
收藏
页码：177 / 183
页数：7
相关论文
共 50 条
  • [21] The complexity of some basic problems for dynamic process graphs
    Jakoby, A
    Liskiewicz, M
    ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2001, 2223 : 562 - 574
  • [22] Injective edge coloring of product graphs and some complexity results
    Bhanupriy, C. K.
    Dominic, Charles
    Sunitha, M. S.
    FILOMAT, 2023, 37 (12) : 3963 - 3983
  • [23] The Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
    Bellitto, Thomas
    Li, Shaohua
    Okrasa, Karolina
    Pilipczuk, Marcin
    Sorge, Manuel
    ALGORITHMICA, 2023, 85 (05) : 1202 - 1250
  • [24] The Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
    Thomas Bellitto
    Shaohua Li
    Karolina Okrasa
    Marcin Pilipczuk
    Manuel Sorge
    Algorithmica, 2023, 85 : 1202 - 1250
  • [25] Some rainbow problems in graphs have complexity equivalent to satisfiability problems
    Hudry, Olivier
    Lobstein, Antoine
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2022, 29 (03) : 1547 - 1572
  • [26] Some Extremal Problems for Edge-Regular Graphs
    Coolsaet, K.
    Johnson, P. D., Jr.
    Roblee, K. J.
    Smotzer, T. D.
    ARS COMBINATORIA, 2012, 105 : 411 - 418
  • [27] Some Results on Edge Coloring Problems with Constraints in Graphs
    Liu, Guizhen
    Hou, Jianfeng
    OPERATIONS RESEARCH AND ITS APPLICATIONS, PROCEEDINGS, 2009, 10 : 6 - 14
  • [28] The complexity of the list partition problem for graphs
    Cameron, Kathie
    Eschen, Elaine M.
    Hoang, Chinh T.
    Sritharan, R.
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2007, 21 (04) : 900 - 929
  • [29] Complexity of graph partition problems
    Feder, Tomas
    Hell, Pavol
    Klein, Sulamita
    Motwani, Rajeev
    Conference Proceedings of the Annual ACM Symposium on Theory of Computing, 1999, : 464 - 472
  • [30] Extension of Some Edge Graph Problems: Standard and Parameterized Complexity
    Casel, Katrin
    Fernau, Henning
    Ghadikolaei, Mehdi Khosravian
    Monnot, Jerome
    Sikora, Florian
    FUNDAMENTALS OF COMPUTATION THEORY, FCT 2019, 2019, 11651 : 185 - 200
12345