On Factorable Extensions and Subgraphs of Prime Graphs

DOI10.1137/0402017zbMath0736.05061OpenAlexW2040668918MaRDI QIDQ4710541

Joan Feigenbaum, Ramsey W. Haddad

Publication date: 25 June 1992

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0402017

zbMATH Keywords

dynamic programming algorithmproduct graphstight boundsNP- completeness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On the weak reconstruction of Cartesian-product graphs ⋮ On optimizing edge connectivity of product graphs ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ Equipartitions of graphs ⋮ Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs ⋮ A local prime factor decomposition algorithm ⋮ Strong products of \(\chi\)-critical graphs ⋮ On the complexity of the embedding problem for hypercube related graphs ⋮ Approximate graph products ⋮ Weak k-reconstruction of cartesian product graphs