Isomorphic tree spanner problems

DOI10.1007/BF01293665MaRDI QIDQ1899446zbMATH OpenFDO

Authors Leizhen Cai, Derek G. Corneil

Publication date 9 October 1995

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

NP-completebipartite graphstree \(t\)-spanner

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Tree Spanners
• scientific article; zbMATH DE number 434687
• scientific article; zbMATH DE number 1262806

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An Analysis of a Good Algorithm for the Subtree Problem
• An Optimal Synchronizer for the Hypercube
• Subtree Isomorphism in O(n5/2)
• The complexity of restricted spanning tree problems
• Tree Spanners

Cited in

(13)

• scientific article; zbMATH DE number 3991551 (Why is no real title available?)
• Tree Spanners
• scientific article; zbMATH DE number 1757963 (Why is no real title available?)
• Pruning by isomorphism in branch-and-cut
• Mixed-integer programming approaches for the tree \(t^*\)-spanner problem
• Edge-disjoint spanners of complete graphs and complete digraphs
• Independent tree spanners: Fault-tolerant spanning trees with constant distance guarantees
• scientific article; zbMATH DE number 3855138 (Why is no real title available?)
• Additive tree 2-spanners of permutation graphs
• scientific article; zbMATH DE number 1335884 (Why is no real title available?)
• scientific article; zbMATH DE number 434687 (Why is no real title available?)
• The Space Complexity of k-Tree Isomorphism
• A linear time algorithm to construct a tree 4-spanner on trapezoid graphs

Describes a project that uses

Uses Software

• CMPT

This page was built for publication: Isomorphic tree spanner problems

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