1. Decomposing Cubic Graphs into Connected Subgraphs of Size Three
- Author
-
Irena Rusu, Laurent Bulteau, Anthony Labarre, Guillaume Fertin, Romeo Rizzi, Department of Software Engineering and Theoretical Computer Science (SWT - TUB), Technische Universität Berlin (TU), Laboratoire d'Informatique de Nantes Atlantique (LINA), Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Department of Computer Science [Verona] (UNIVR | DI), University of Verona (UNIVR), Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Università degli studi di Verona = University of Verona (UNIVR), and Labarre, Anthony
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,FOS: Computer and information sciences ,Computational complexity theory ,Combinatorial mathematics ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,02 engineering and technology ,Input graphs ,NP Complete ,01 natural sciences ,Combinatorics ,Computer Science - Data Structures and Algorithms ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,0202 electrical engineering, electronic engineering, information engineering ,FOS: Mathematics ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,Cubic graph ,Edge-sets ,Mathematics ,General graph ,Connected graph ,020206 networking & telecommunications ,Graph ,Traffic grooming ,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO] ,Computational complexity ,Graph theory ,Graph theory, Connected graph ,Connected subgraphs ,Graph-theoretic ,NP Complete, Graphic methods ,010201 computation theory & mathematics ,Graphic methods ,[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] ,Combinatorics (math.CO) ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
Let $S=\{K_{1,3},K_3,P_4\}$ be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph $G$ into graphs taken from any non-empty $S'\subseteq S$. The problem is known to be NP-complete for any possible choice of $S'$ in general graphs. In this paper, we assume that the input graph is cubic, and study the computational complexity of the problem of partitioning its edge set for any choice of $S'$. We identify all polynomial and NP-complete problems in that setting, and give graph-theoretic characterisations of $S'$-decomposable cubic graphs in some cases., Comment: to appear in the proceedings of COCOON 2016
- Published
- 2016
- Full Text
- View/download PDF