Skip to main content
Springer Nature Link
Log in

Maximum Flows and Critical Vertices in AND/OR Graphs

Extended Abstract

  • Conference paper
  • First Online:
Computing and Combinatorics (COCOON 2002)

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

Included in the following conference series:

Abstract

We will study this problem and present an algorithm for finding the minimum-time-cost solution graph in an AND/OR graph. We will also study the following problems which often appear in industry when using AND/OR graphs to model manufacturing processes or to model problem solving processes: finding maximum (additive and non-additive) flows and critical vertices in an AND/OR graph. Though there are well known polynomial time algorithms for the corresponding problems in the traditional graph theory, we will show that generally it is NP-hard to find a non-additive maximum flow in an AND/OR graph, and it is both NP-hard and coNP-hard to find a set of critical vertices in an AND/OR graph. We will also present a polynomial time algorithm for finding a maximum additive flow in an AND/OR graph, and discuss the relative complexity of these problems.

Research supported by DARPA F30602-97-1-0205.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 85.59
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 105.49
Price includes VAT (France)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. M. Burmester, Y. Desmedt, and Y. Wang. Using approximation hardness to achieve dependable computation. In: Proc. RANDOM’ 98, pages 172–186. LNCS 1518, Springer Verlag, 1998.

    Google Scholar 

  2. C. L. Chang and J. R. Slagle. An admissible and optimal algorithm for searching AND/OR graphs. Artificial Intelligence, 2:117–128, 1971.

    Article  MATH  MathSciNet  Google Scholar 

  3. L.R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, NJ, 1962.

    MATH  Google Scholar 

  4. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco, 1979.

    Google Scholar 

  5. M. Gondran and M. Minoux. Graphs and Algorithms. John Wiley & Sons Ltd., New York, 1984.

    MATH  Google Scholar 

  6. D. Hvalica. Best first search algorithm in AND/OR graphs with cycles. J. of Algorithms, 21:102–110, 1996.

    Article  MATH  MathSciNet  Google Scholar 

  7. A. Martelli and U. Montanari. Additive AND/OR graphs. In Proceedings of the Third International Joint Conference on Artificial Intelligence, pages 1–11, Morgan Kaufmann Publishers, Inc., 1973.

    Google Scholar 

  8. N. J. Nilsson. Principles of Artificial Intelligence. Tioga, 1980.

    Google Scholar 

  9. S. Sahni. Computationally related problems. SIAM J. Comput., 3:262–279, 1974.

    Article  MathSciNet  Google Scholar 

  10. Y. Wang, Y. Desmedt, and M. Burmester. NP-Hardness of dependable computation with multiple inputs. Fundamenta Informaticae, 42(1):61–73, 2000.

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science, Florida State University, Tallahassee, Florida, FL, 32306-4530, USA

    Yvo Desmedt

  2. Department of Mathematics, Royal Holloway, University of London, UK

    Yvo Desmedt

  3. Department of Software and Information Systems, University of North Carolina at Charlotte, 9201, University City Blvd, Charlotte, NC, 28223

    Yongge Wang

Authors
  1. Yvo Desmedt
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yongge Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of California, Santa Barbara, California, 93106, USA

    Oscar H. Ibarra

  2. Department of Mathematics, National University of Singapore, Singapore, Singapore, 117543

    Louxin Zhang

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Desmedt, Y., Wang, Y. (2002). Maximum Flows and Critical Vertices in AND/OR Graphs. In: Ibarra, O.H., Zhang, L. (eds) Computing and Combinatorics. COCOON 2002. Lecture Notes in Computer Science, vol 2387. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45655-4_27

Download citation

  • DOI: https://doi.org/10.1007/3-540-45655-4_27

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-43996-7

  • Online ISBN: 978-3-540-45655-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation