[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

A Note on n-Critical Bipartite Graphs and Its Application

  • Conference paper
Combinatorial Optimization and Applications (COCOA 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5573))

  • 1214 Accesses

Abstract

In matching theory, n-critical graphs play an important role in the decomposition of graphs with respect to perfect matchings. Since bipartite graphs cannot be n-critical when n > 0, we amend the classical definition of n-critical graphs and propose the concept of n-critical bipartite graphs. Let G = (B,W; E) be a bipartite graph with n = |W| − |B|, where B and W are the bipartitions of vertex set, E is the edge set. Then, G is n-critical if when deleting any n distinct vertices of W, the remaining subgraph of G has a perfect matching. Furthermore, an algorithm for determining n-critical bipartite graphs is given which runs in O(|W||E|) time, in the worst case. Our work helps to design a job assignment circuit which has high robustness.

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
£29.99 /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
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 72.00
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

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. Favaron, O.: On k-Critical Graphs. Discuss. Math. Graph Theory 16, 41–51 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  2. Favaron, O.: Extendability and Factor-Criticality. Discrete Math. 213, 115–122 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  3. Gabow, H., Jordan, T.: How to Make a Square Grid Framework with Cables Rigid. SIAM Journal of Computing 30, 649–680 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  4. Li, Y., Lou, D.: Matching Extendability Augmentation in Bipartite Graphs. In: International Multiconference of Engineers and Computer Scientists (IMECS 2007), IAENG, Hongkong, pp. 2291–2296 (2007)

    Google Scholar 

  5. Li, Y., Lou, D.: Finding the (n,k,0)-Extendability in Bipartite Graphs and its Application. In: Shi, Y., van Albada, G.D., Dongarra, J., Sloot, P.M.A. (eds.) ICCS 2007. LNCS, vol. 4489, pp. 401–409. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  6. Liu, G., Yu, Q.: Generlization of Matching Extensions in Graphs. Discrete Math. 231, 311–320 (2001)

    Article  MathSciNet  Google Scholar 

  7. Plummer, M.: Extending Matchings in Graphs: a Survey. Discrete Math. 127, 277–292 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  8. Plummer, M.: Extending Matchings in Graphs: an Update. Congr. Numer. 116, 3–32 (1996)

    MathSciNet  MATH  Google Scholar 

  9. Plummer, M.: Matching Extension in Bipartite Graphs. Congr. Numer. 54, 245–258 (1986)

    MathSciNet  MATH  Google Scholar 

  10. Yu, Q.: Characterizations of Various Matching Extensions in Graphs. Australas. J. Combin. 7, 55–64 (1993)

    MathSciNet  MATH  Google Scholar 

  11. Zhang, F., Zhang, H.: Construction for Bicritical Graphs and k-Extendable Bipartite Graphs. Discrete Math. 306, 1415–1423 (2006)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Electronics and Information Engineering, Shenzhen Polytechnic, Shenzhen, 518055, China

    Yueping Li & Zhe Nie

Authors
  1. Yueping Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zhe Nie
    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 Texas at Dallas, 800 West Campbell Road, TX 75080-3021, Richardson, USA

    Ding-Zhu Du

  2. Chinese Academy of Sciences, Institute of Applied Mathematics, Zhong Guan Cun Dong Lu 55, 100190, Beijing, P. R. China

    Xiaodong Hu

  3. Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, P.O. Box 116595, FL 32611-6595, Gainesville, USA

    Panos M. Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Li, Y., Nie, Z. (2009). A Note on n-Critical Bipartite Graphs and Its Application. In: Du, DZ., Hu, X., Pardalos, P.M. (eds) Combinatorial Optimization and Applications. COCOA 2009. Lecture Notes in Computer Science, vol 5573. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02026-1_26

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-02026-1_26

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-02025-4

  • Online ISBN: 978-3-642-02026-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation