Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Min-Max Relation on Packing Feedback Vertex Sets

  • Conference paper
Algorithms and Computation (ISAAC 2005)

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

Included in the following conference series:

Abstract

Let G be a graph with a nonnegative integral function w defined on V(G). A family \(\mathcal{F}\) of subsets of V(G) (repetition is allowed) is called a feedback vertex set packing in G if the removal of any member of \(\mathcal{F}\) from G leaves a forest, and every vertex v∈ V(G) is contained in at most w(v) members of \(\mathcal{F}\). The weight of a cycle C in G is the sum of w(v), over all vertices v of C. In this paper we characterize all graphs with the property that, for any nonnegative integral function w, the maximum cardinality of a feedback vertex set packing is equal to the minimum weight of a cycle.

Supported in part by: 1The NSF of China under Grant No. 70221001 and 60373012, 2NSA grant H98230-05-1-0081, NSF grant ITR-0326387, and AFOSR grant: F49620-03-1-0239-0241, and 3The Research Grants Council of Hong Kong.

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
$34.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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • 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. Ding, G., Zang, W.: Packing cycles in graphs. J. Combin. Theory Ser. B 86, 381–407 (2003)

    Article  MathSciNet  Google Scholar 

  2. Ding, G., Xu, Z., Zang, W.: Packing cycles in graphs, II. J. Combin. Theory Ser. B 87, 244–253 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  3. Edmonds, J., Giles, R.: A min-max relation for submodular functions on graphs. Annals of Discrete Math. 1, 185–204 (1977)

    Article  MathSciNet  Google Scholar 

  4. Fulkerson, D.R.: Blocking and anti-blocking pairs of polyhedra. Mathematical Programming 1, 168–194 (1971)

    Article  MATH  MathSciNet  Google Scholar 

  5. Guenin, B.: Oral communication (2000)

    Google Scholar 

  6. Schrijver, A.: Combinatorial Optimization - Polyhedra and Efficiency. Springer, Heidelberg (2003)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Applied Mathematics, Chinese Academy of Sciences, P.O. Box 2734, Beijing, 100080, China

    Xujin Chen & Xiaodong Hu

  2. Mathematics Department, Louisiana State University, Baton Rouge, Louisiana, USA

    Guoli Ding

  3. Department of Mathematics, The University of Hong Kong, Hong Kong, China

    Wenan Zang

Authors
  1. Xujin Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guoli Ding
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiaodong Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wenan Zang
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon , Hong Kong

    Xiaotie Deng

  2. Department of Computer Science, University of Texas at Dallas, EE/CS Building, 75083, Richardson, TX, USA

    Ding-Zhu Du

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Chen, X., Ding, G., Hu, X., Zang, W. (2005). A Min-Max Relation on Packing Feedback Vertex Sets. In: Deng, X., Du, DZ. (eds) Algorithms and Computation. ISAAC 2005. Lecture Notes in Computer Science, vol 3827. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11602613_14

Download citation

  • DOI: https://doi.org/10.1007/11602613_14

  • Publisher Name: Springer, Berlin, Heidelberg

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

  • Online ISBN: 978-3-540-32426-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation