On the complexity of recognizing \(S\)-composite and \(S\)-prime graphs
From MaRDI portal
Publication:1949105
DOI10.1016/j.dam.2012.11.003zbMath1262.05054arXiv1205.0991OpenAlexW1966279619MaRDI QIDQ1949105
Publication date: 25 April 2013
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1205.0991
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)
Related Items (3)
Global rigidity of (quasi-)injective frameworks on the line ⋮ Fast factorization of Cartesian products of (directed) hypergraphs ⋮ Strong products of hypergraphs: unique prime factorization theorems and algorithms
Cites Work
- A local prime factor decomposition algorithm
- Diagonalized Cartesian products of \(S\)-prime graphs are \(S\)-prime
- Recognizing Cartesian products in linear time
- On subgraphs of Cartesian product graphs
- On subgraphs of Cartesian product graphs and S-primeness
- A new concept of primeness in graphs
- Characterizing subgraphs of Hamming graphs
- The complexity of satisfiability problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the complexity of recognizing \(S\)-composite and \(S\)-prime graphs
