On the arrangement complexity of uniform trees | SpringerLink
Skip to main content
Springer Nature Link
Log in

On the arrangement complexity of uniform trees

  • Chapter
  • First Online:
Foundations of Computer Science

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1337))

  • 269 Accesses

Abstract

This paper studies the arrangement problem of uniform trees and shows that the arrangement complexity of a uniform tree is either θ(1) or Ω((lg n)γ)(γ > 0). It also presents a recursive algorithm to compute the optimal complete arrangements for θ(1) arrangeable balanced uniform trees.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. B. Becker, and J. Hartmann. Optimal-Time Multipliers and C-Testability. Proceedings of the 2nd Annual Symposium on Parallel Algorithms and Architectures, pp.146–154, 1990.

    Google Scholar 

  2. B. Becker, and U. Sparmann. Computations over Finite Monoids and their Test Complexity. Theoretical Computer Science, pp.225–250, 1991.

    Google Scholar 

  3. R. Fritzemeier, J. Soden, R. K. Treece, and C. Hawkins. Increased CMOS IC stuck-at fault coverage with reduced IDDQ test sets. International Test Conference, pp.427–435, 1990

    Google Scholar 

  4. J. P. Hayes. On Realizations of Boolean Functions Requiring a Minimal or Near-Minimal Number of Tests. IEEE Trans. on Computers Vol. C-20, No. 12, pp.1506–1513, 1971.

    MathSciNet  Google Scholar 

  5. G. Hotz. Eine Algebraisierung des Syntheseproblems von Schaltkreisen. EIK 1, 185–205, 209–231, 1965.

    MATH  MathSciNet  Google Scholar 

  6. G. Hotz. Schaltkreistheorie. Walter de Gruyter · Berlin · New York 1974.

    MATH  Google Scholar 

  7. G. Hotz, H. Wu. “On the Arrangement Complexity of Uniform Trees”, Technical Report, SFB 124-B1, 05/1995, FB-14, Informatik, Universität des Saarlandes, Germany.

    Google Scholar 

  8. S. C. Seth, and K.L. Kodandapani. Diagnosis of Faults in Linear Tree Networks. IEEE Trans. on Computers, C-26(1), pp.29–33, 1977.

    Article  MathSciNet  Google Scholar 

  9. H. Wu. On Tests of Uniform Tree Circuits. Proceeding of CONPAR VAPP V, pp.527–538, 1992.

    Google Scholar 

  10. H. Wu, U. Sparmann. On the Assignments Complexity of Tree VLSI Systems. Proceeding of 7th International Symposium on Computer and Information Sciences, pp.97–103, 1992.

    Google Scholar 

  11. H. Wu. On the Assignments Complexity of Uniform Trees. Proceeding of International Symposium on Symbolic and Algebraic Computation, ISSAC' 93, pp.95–104.

    Google Scholar 

  12. H. Wu. On the Test Complexity of VLSI Systems, Dissertation, University of Saarland, 1994

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. 14-Informatik, Universität des Saarlandes, Deutschland

    Günter Hotz & Hongzhong Wu

Authors
  1. Günter Hotz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hongzhong Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Christian Freksa Matthias Jantzen Rüdiger Valk

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Hotz, G., Wu, H. (1997). On the arrangement complexity of uniform trees. In: Freksa, C., Jantzen, M., Valk, R. (eds) Foundations of Computer Science. Lecture Notes in Computer Science, vol 1337. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052102

Download citation

  • DOI: https://doi.org/10.1007/BFb0052102

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-63746-2

  • Online ISBN: 978-3-540-69640-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation