scientific article; zbMATH DE number 2170471

MaRDI QIDQ4677967zbMATH OpenFDO

Authors Etsuro Moriya

Publication date 23 May 2005

zbMATH Keywords

connected graphNP-completeP-complete

Mathematics Subject Classification ID

Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On counting and approximation variants of the subgraph connecting problem
• On the complexity of partitioning graphs into connected subgraphs
• Parallel Complexity of the Connected Subgraph Problem
• On complexity of subset interconnection designs
• On the complexity of the maximum subgraph problem

Cited in

(1)

• On counting and approximation variants of the subgraph connecting problem

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4677967)