On the computational complexity of graph closures

DOI10.1016/0020-0190(96)00027-0MaRDI QIDQ1351617zbMATH OpenOpenAlexFDO

Authors Angelo Monti

Publication date 27 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(96)00027-0

zbMATH Keywords

P-completenessComputational complexityGraph closureParallel complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On computing graph closures
• A note on computing graph closures
• On graph closures
• A note on the computation on the k-closure of a graph
• On a certain complexity estimate in graph theory
• scientific article; zbMATH DE number 4152420
• On Graph Complexity
• scientific article; zbMATH DE number 3876594
• A New Algorithm for Computing the Maximal Closure of a Graph
• scientific article; zbMATH DE number 7300406

Cites work

• scientific article; zbMATH DE number 3708436 (Why is no real title available?)
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• A method in graph theory
• On computing graph closures
• The maximum flow problem is log space complete for P

Cited in

(7)

• Exploiting c-Closure in Kernelization Algorithms for Graph Problems
• A note on computing graph closures
• A note on the fast computation of transitive closure of graphs and the multiplication of integer matrices
• On graph closures
• scientific article; zbMATH DE number 219266 (Why is no real title available?)
• A New Algorithm for Computing the Maximal Closure of a Graph
• The complexity of learning minor closed graph classes

This page was built for publication: On the computational complexity of graph closures

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