The Serial Transitive Closure Problem for Trees

DOI10.1137/S0097539792225303MaRDI QIDQ4326856zbMATH OpenOpenAlexFDO

Authors Maria Luisa Bonet, Samuel R. Buss

Publication date 27 March 1995

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmserial transitive closure problemweak superconcentrators

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Closure and spanning \(k\)-trees
• Sequences of spanning trees and a fixed tree theorem
• Tree canonization and transitive closure
• scientific article; zbMATH DE number 7267318
• scientific article; zbMATH DE number 1305085
• On the status sequences of trees
• The general \(\sigma \) all-ones problem for trees
• Trees and Keisler's problem
• Closure and spanning trees with bounded total excess
• Analogs & duals of the MAST problem for sequences & trees

Cited in

(3)

• Inverse problems of transitive closure
• Generalisation of proof simulation procedures for Frege systems by M. L. Bonet and S. R. Buss
• Shortcutting directed and undirected networks with a degree constraint

This page was built for publication: The Serial Transitive Closure Problem for Trees

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