Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms | SpringerLink
Skip to main content
Springer Nature Link
Log in

Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms

  • Conference paper
Parameterized and Exact Computation (IWPEC 2006)

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

Included in the following conference series:

Abstract

Matching and packing problems have formed an important class of NP-hard problems. There have been a number of recently developed techniques for parameterized algorithms for these problems, including greedy localization, color-coding plus dynamic programming, and randomized divide-and-conquer. In this paper, we provide further theoretical study on the structures of these problems, and develop improved algorithmic methods that combine existing and new techniques to obtain improved algorithms for matching and packing problems. For the 3-set packing problem, we present a deterministic algorithm of time O *(4.613k), which significantly improves the previous best deterministic algorithm of time O *(12.83k). For the 3-d matching problem, we develop a new randomized algorithm of running time O *(2.323k) and a new deterministic algorithm of running time O *(2.773k). Our randomized algorithm improves the previous best randomized algorithm of running time O *(2.523k), and our deterministic algorithm significantly improves the previous best deterministic algorithm of running time O *(12.83k). Our results also imply improved algorithms for various triangle packing problems in graphs.

This work was supported in part by the National Science Foundation under the Grants CCR-0311590 and CCF-0430683.

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • 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. Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Struct. Alg. 3, 289–304 (1992)

    Article  MATH  Google Scholar 

  2. Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42, 844–856 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  3. Chen, J., Friesen, D.K., Jia, W., Kanj, I.A.: Using nondeterminism to design efficient deterministic algorithms. Algorithmica 40, 83–97 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  4. Chen, J., Lu, S., Sze, S.-H., Zhang, F.: Improved algorithms for path, matching, and packing problems (manuscript, 2006)

    Google Scholar 

  5. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)

    MATH  Google Scholar 

  6. Dehne, F., Fellows, M., Rosamond, F.A., Shaw, P.: Greedy localization, iterative compression, and modeled crown reductions: new FPT techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 271–280. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  7. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)

    Google Scholar 

  8. Fellows, M., Heggernes, P., Rosamond, F.A., Sloper, C., Telle, J.A.: Finding k disjoint triangles in an arbitrary graph. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 235–244. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  9. Fellows, M.R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F.A., Stege, U., Thilikos, D.M., Whitesides, S.H.: Faster fixed-parameter tractable algorithms for matching and packing problems. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 311–322. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  10. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)

    MATH  Google Scholar 

  11. Jia, W., Zhang, C., Chen, J.: An efficient parameterized algorithm for m-set packing. J. Alg. 50, 106–117 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  12. Kneis, J., Mölle, D., Richter, S., Rossmanith, P.: Divide-and-color. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 58–67. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  13. Koutis, I.: A faster parameterized algorithm for set packing. Inf. Process. Lett. 94, 7–9 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  14. Mathieson, L., Prieto, E., Shaw, P.: Packing edge disjoint triangles: A parameterized view. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 127–137. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  15. Prieto, E., Sloper, C.: Looking at the stars. Theor. Comp. Sci. 351, 437–445 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  16. Schmidt, J.P., Siegel, A.: The spatial complexity of oblivious k-probe hash functions. SIAM J. Comp. 19, 775–786 (1990)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science,  

    Yang Liu, Songjian Lu, Jianer Chen & Sing-Hoi Sze

  2. Department of Biochemistry & Biophysics, Texas A&M University, College Station, TX, 77843, USA

    Sing-Hoi Sze

Authors
  1. Yang Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Songjian Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jianer Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Sing-Hoi Sze
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Information and Computing Sciences, Utrecht University, The Netherlands

    Hans L. Bodlaender

  2. University of Tennessee, 37996-3450, Knoxville, Tennessee, U.S.A.

    Michael A. Langston

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Liu, Y., Lu, S., Chen, J., Sze, SH. (2006). Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms. In: Bodlaender, H.L., Langston, M.A. (eds) Parameterized and Exact Computation. IWPEC 2006. Lecture Notes in Computer Science, vol 4169. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11847250_8

Download citation

  • DOI: https://doi.org/10.1007/11847250_8

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-39098-5

  • Online ISBN: 978-3-540-39101-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation