[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 simple optimal algorithm for k-tuple dominating problem in interval graphs

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

In this paper, we study the k-tuple domination in interval graphs from an algorithmic point of view. We present a linear time algorithm to solve the k-tuple domination problem in interval graphs for any positive integer k. Surprisingly, the time complexity of our algorithm is not related to k. This generalizes and extends the results of Pramanik et al. (Int J Comb 2011:14, 2011).

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

Access this article

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

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Data availability statement

Enquiries about data availability should be directed to the authors.

References

  • Argiroffo G, Leoni V, Torres P (2018) Complexity of k-tuple total and total k-dominations for some subclasses of bipartite graphs. Inf Process Lett 138:75–80

    Article  MathSciNet  MATH  Google Scholar 

  • Barman SC, Mondal S, Pal M (2013) Minimum 2-tuple dominating set of permutation graphs. J Appl Math Comput 43:133–150

    Article  MathSciNet  MATH  Google Scholar 

  • Belmonte R, Vatshelle M (2013) Graph classes with structured neighborhoods and algorithmic applications. Theor Comput Sci 511:54–65

    Article  MathSciNet  MATH  Google Scholar 

  • Booth KS, Lueker GS (1976) Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms. J Comput Syst Sci 13:335–379

    Article  MathSciNet  MATH  Google Scholar 

  • Bui-Xuan BM, Telle JA, Vatshelle M (2013) Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor Comput Sci 511:66–76

    Article  MathSciNet  MATH  Google Scholar 

  • Chellali M, Meddah N (2012) Trees with equal 2-domination and 2-independence numbers. Discuss Math Graph Theory 32(2):263–270

    Article  MathSciNet  MATH  Google Scholar 

  • Chellali M, Favaron O, Hansberg A, Volkmann L (2012) k-domination and k-independence in graphs, a survey. Graphs Comb 28(1):1–55

    Article  MathSciNet  MATH  Google Scholar 

  • Chiarelli N, Hartinger TR, Leoni VA, Pujato MIL, Milanic M (2019) New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs. Theor Comput Sci 795:128–141

    Article  MathSciNet  MATH  Google Scholar 

  • Cicalese F, Milanic M, Vaccaro U (2013) On the approximability and exact algorithms for vector domination and related problems in graphs. Discrete Appl Math 161(6):750–767

    Article  MathSciNet  MATH  Google Scholar 

  • Corneil DG, Olariu S, Stewart L (2009) The LBFS structure and recognition of interval graphs. SIAM J Discrete Math 23:1905–1953

    Article  MathSciNet  MATH  Google Scholar 

  • Favaron O, Hansberg A, Volkmann L (2008) On k-domination and minimum degree in graphs. J Graph Theory 57(1):33–40

    Article  MathSciNet  MATH  Google Scholar 

  • Fink JF, Jacobson MS (1984) n-domination in graphs, Graph Theory With Applications to Algorithms and Computer Science, Kalamazoo, Mich., Wiley Interscience Publisher Wiley, New York 1985, pp 283–300

  • Fishburn PC (1985) Interval orders and interval graphs: a study of partially ordered sets. Wiley, New York

    Book  MATH  Google Scholar 

  • Golumbic MC (2004) Algorithmic graph theory and perfect graphs. Annals of discrete mathematics, vol 57, 2nd edn. Elsevier, Amsterdam

    Google Scholar 

  • Hansberg A, Pepper R (2013) On k-domination and j-independence in graphs. Discrete Appl Math 161(10–11):1472–1480

    Article  MathSciNet  MATH  Google Scholar 

  • Harary F, Haynes TW (2000) Double domination in graphs. Ars Comb 55:201–213

    MathSciNet  MATH  Google Scholar 

  • Haynes TW, Hedetniemi ST, Slater PJ (1998) Domination in graphs: advanced topics. Marcel Dekker Inc, New York

    MATH  Google Scholar 

  • Haynes TW, Hedetniemi ST, Slater PJ (1998) Fundamentals of domination in graphs. Marcel Dekker Inc, New York

    MATH  Google Scholar 

  • Henning MA, Kazemi AP (2010) k-tuple total domination in graphs. Discrete Appl Math 158:1006–1011

    Article  MathSciNet  MATH  Google Scholar 

  • Jacobson M.S, Peters K (1989) Complexity questions for n-domination and related parameters. In: Eighteenth Manitoba conference on numerical mathematics and computing, Winnipeg, MB, 1988, Congruent Number, vol 68, pp 7–22

  • Kang DY, Kwon O-J, Stromme TJF, Telle JA (2017) A width parameter useful for chordal and co-comparability graphs. Theore Comput Sci 704:1–17

    Article  MathSciNet  MATH  Google Scholar 

  • Kazemi AP (2012) On the total k-domination number of graphs. Discuss Math Graph Theory 32(3):419–426

    Article  MathSciNet  MATH  Google Scholar 

  • Kulli VR (1991) On n-total domination number in graphs. In: Graph theory, combinatorics, algorithms, and applications, San Francisco, CA, 1989. PA, SIAM, Philadelphia, pp 319–324

  • Lan JK, Chang GJ (2013) Algorithmic aspects of the k-domination problem in graphs. Discrete Appl Math 161(10–11):1513–1520

    Article  MathSciNet  MATH  Google Scholar 

  • Lan JK, Chang GJ (2014) On the algorithmic complexity of k-tuple total domination. Discrete Appl Math 174:81–91

    Article  MathSciNet  MATH  Google Scholar 

  • Li P, Wu Y (2015) Spanning connectedness and Hamiltonian thickness of graphs and interval graphs. Discrete Math Theor Comput Sci 16(2):125–210

    Article  MathSciNet  MATH  Google Scholar 

  • Li P, Wu Y (2017) A linear time algorithm for the 1-fixed-endpoint path cover problem on interval graphs. SIAM J Discrete Math 31(1):210–239

    Article  MathSciNet  MATH  Google Scholar 

  • Looges PJ, Olariu S (1993) Optimal greedy algorithms for indifference graphs. Comput Math Appl 25:15–25

    Article  MathSciNet  MATH  Google Scholar 

  • Möhring RH (1985) Algorithmic aspects of comparability graphs and interval graphs. In: Rival I (ed) Graphs and Orders. D. Reidel, Boston, pp 41–101

    Chapter  Google Scholar 

  • Pradhan D (2012) Algorithmic aspects of k-tuple total domination in graphs. Inf Process Lett 112(21):816–822

    Article  MathSciNet  MATH  Google Scholar 

  • Pramanik T, Mondal S, Pal M, Minimum 2-tuple dominating set of an interval graph. Int J Comb, Volume 2011, Article ID 389369, 14 pages

  • Ramalingam G, Rangan CP (1988) A uniform approach to domination problems on interval graphs. Inf Process Lett 27:271–274

    Article  MATH  Google Scholar 

  • Raychaudhuri A (1987) On powers of interval and unit interval graphs. Congr Numer 59:235–242

    MathSciNet  MATH  Google Scholar 

  • Shang J, Li P, Shi Y (2021) The longest cycle problem is polynomial on interval graphs. Theor Comput Sci 859:37–47

    Article  MathSciNet  MATH  Google Scholar 

  • Trotter WT (1997) New perspectives on interval orders and interval graphs. In: Bailey RA (ed) Surveys in combinatorics. London mathematical society lecture note series, vol 241. Cambridge University Press, Cambridge, pp 237–286

    Google Scholar 

  • Yang S, Wang H A note on the 2-tuple total domination problem in Harary graphs. In: 2016 International computer symposium

Download references

Acknowledgements

We thank the referees and editors for their constructive input.

Funding

This work was supported by the National Natural Science Foundation of China (11701059), Natural Science Foundation of Chongqing (cstc2019jcyj-msxmX0156, cstc2020jcyj-msxmX0272, cstc2021jcyj-msxmX0436) and the Youth project of science and technology research program of Chongqing Education Commission of China (KJQN202001107, KJQN202001130, KJQN202101130).

Author information

Authors and Affiliations

  1. Chongqing University of Technology, 69 Hongguang Avenue, Chongqing, China

    Peng Li & Aifa Wang

  2. Shanghai Jiao Tong University, 800 Dongchuan Avenue, Shanghai, China

    Jianhui Shang

Authors
  1. Peng Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Aifa Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jianhui Shang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Aifa Wang.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, P., Wang, A. & Shang, J. A simple optimal algorithm for k-tuple dominating problem in interval graphs. J Comb Optim 45, 14 (2023). https://doi.org/10.1007/s10878-022-00932-4

Download citation

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10878-022-00932-4

Keywords

Search

Navigation