Research Article
BibTex RIS Cite

Finding Innovative and Efficient Solutions to NP-Hard and NP-Complete Problems in Graph Theory

Year 2020, Volume: 5 Issue: 2, 137 - 143, 01.12.2020

Abstract

It is known that there are many NP-hard and
NP-complete problems in graph theory. The aim of this paper to prepare some
basic methods for solving such problems (min dominating set, max independent
set, max clique, etc.). In order to construct such fundamentals, the
effectiveness and ineffectiveness of all nodes in the given graph are computed.
Then these values will be used in solving NP-Hard problems of graphs.

References

  • Alikhan, S., Peng, Y.-H., “Construction of Dominating Sets of Certain Graphs”, Journal of Discrete Mathematics, Vol:2013, Article ID:587196, 2013.
  • Brandstadt, A., Mosca, R., “Maximum weight independent set for Lclaw-free graphs in polynomial time”, Discrete Applied Mathematics, Vol:237, pp:57-64, 2018.
  • Bresar, B., Movarraei, N., “On the number of maximal independent sets in minimum colorings of split graphs”, Discrete Applied Mathematics, Vol:247, pp:352-356, 2018.
  • Bron, C., Kerbosch, J.,”Algorithm 457: Finding all cliques of an undirected graph”, ACM Communication, Vol:16, pp:575-577, 1973. Connolly, S., Gabor, Z., Godbole, A., Kay, B., Kelly, T.,”Bounds on the Maximum Number of Minimum Dominating Sets”, Discrete Mathematics, Vol:339, pp:1537-1542, 2016.
  • Deng, Y.-P., Sun, Y.-Q., Liu, Q., Wang, H.-C.,”Efficient Dominating Sets in Circular Graphs”, Discrete Mathematics, Vol:340, pp:1503-1507, 2017.
  • Goddard, W., Henning, M.A., “Independent domination in Graphs: A Survey and Recent Results”, Discrete Mathematics, Vol: 313, pp:839-854, 2013.
  • Golovach, P.A., Heggernes, P., Kante, M.M., Kratsch, D., Villanger, Y.,”Enumerating Minimal Dominating Sets in Chordal Bipartite Graphs”, Discrete Applied Mathematics, Vol:199, pp:30-36, 2016.
  • Jarden, A., Levit, V.E., Mandrescu, E.,”Critical and maximum independent sets of a graph”, Discrete Applied Mathematics, Vol: 247, pp:127-134, 2018.
  • Karci, A., Karci, Ş.,”Determination of Effective Nodes in Graphs”, International Conference on Science, Engineering & Technology, Mecca, Saudi Arabia, pp:25-28, 2020.
  • Laflamme, C., Aranda, A., Soukup, D.T., Woodrow, R.,”Balanced independent sets in graphs omitting large cliques”, Journal of Combinatorial Theory, Series B, Vol:137, pp:1-9, 2019.
  • Lin, M.-S.,”Counting independent sets and maximal independent sets in some subclasses of bipartite graphs”, Discrete Applied Mathematics, Vol:251, pp:236-244, 2018a.
  • Lin. M.-S., “Simple linear-time algorithms for counting independent sets in distance-hereditary graphs”, Discrete Applied Mathematics, Vol: 239, pp:144-153, 2018b.
  • Lin, M.-S., Chen, C.-M.,”Linear-time algorithms for counting independent sets in bipartite permutation graphs”, Information Processing Letters, Vol:122, pp:1-7, 2017.
  • Marti-Farre, J., Mora, M., Ruiz, J. L.,”Uniform Clutters and Dominating Sets of Graphs”, Discrete Applied Mathematics, Vol:263, pp:220-233, 2019.
  • Naude, K.A.,”Refined pivot selection for maximal clique enumeration in graphs”, Theoretical Computer Science, vol:613, pp:28-37, 2016. Oh, S., “Maximal independent sets on a grid graph”, Discrete Mathematics, Vol:340, pp:2762-2768, 2017.
  • Peramau, G., Perkins, W.,”Counting independent sets in cubic graphs of given girth”, Journal of Combinatorial Theory, Series B, Vol:133, pp:2018.
  • Rooij, J.van, Bodlaender, H.L., “Exact algorithms for dominating set”, Discrete Applied Mathematics, Vol:159, pp:2147-2164, 2011.
  • Sah, A., Sawhhney, M., Stoner, D., Zhao, Y.,”The number of independent sets in an irregular graph”, Journal of Combinatorial Theory, Series B, Vol:138, pp:172-195, 2019.
  • Thulasiraman, K.KT., Arumugan, S., Brandstadt, A., Nishizeki, T., “Handbook of Graph Theory, Combinatorial Optimization and Algorithms”, CRC Press, Sendai, Japan, 2016.
  • Wan, P., Tu, J., Zhang, S., Li, B., “Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth”, Applied Mathematics and Computation, Vol:332, pp:42-47, 2018.
  • Wan, P., Chen, X., Tu, J., Dehmer, M., Zhang, S., Emmert-Streib, F.,”On graph entropy measures based on the number of independent sets and matchings”, Information Sciences, Vol:516, pp:491-504, 2020.
  • Yu,T., Liu, M.,”a linear time algorithm for maximal clique enumeration in large sparse graphs”, Information Processing Letters, vol:125, pp:35-40, 2017.

Finding Innovative and Efficient Solutions to NP-Hard and NP-Complete Problems in Graph Theory

Year 2020, Volume: 5 Issue: 2, 137 - 143, 01.12.2020

Abstract

It is known that there are many NP-hard and NP-complete problems in graph theory. The aim of this paper to prepare some basic methods for solving such problems (min dominating set, max independent set, max clique, etc.). In order to construct such fundamentals, the effectiveness and ineffectiveness of all nodes in the given graph are computed. Then these values will be used in solving NP-Hard problems of graphs.

References

  • Alikhan, S., Peng, Y.-H., “Construction of Dominating Sets of Certain Graphs”, Journal of Discrete Mathematics, Vol:2013, Article ID:587196, 2013.
  • Brandstadt, A., Mosca, R., “Maximum weight independent set for Lclaw-free graphs in polynomial time”, Discrete Applied Mathematics, Vol:237, pp:57-64, 2018.
  • Bresar, B., Movarraei, N., “On the number of maximal independent sets in minimum colorings of split graphs”, Discrete Applied Mathematics, Vol:247, pp:352-356, 2018.
  • Bron, C., Kerbosch, J.,”Algorithm 457: Finding all cliques of an undirected graph”, ACM Communication, Vol:16, pp:575-577, 1973. Connolly, S., Gabor, Z., Godbole, A., Kay, B., Kelly, T.,”Bounds on the Maximum Number of Minimum Dominating Sets”, Discrete Mathematics, Vol:339, pp:1537-1542, 2016.
  • Deng, Y.-P., Sun, Y.-Q., Liu, Q., Wang, H.-C.,”Efficient Dominating Sets in Circular Graphs”, Discrete Mathematics, Vol:340, pp:1503-1507, 2017.
  • Goddard, W., Henning, M.A., “Independent domination in Graphs: A Survey and Recent Results”, Discrete Mathematics, Vol: 313, pp:839-854, 2013.
  • Golovach, P.A., Heggernes, P., Kante, M.M., Kratsch, D., Villanger, Y.,”Enumerating Minimal Dominating Sets in Chordal Bipartite Graphs”, Discrete Applied Mathematics, Vol:199, pp:30-36, 2016.
  • Jarden, A., Levit, V.E., Mandrescu, E.,”Critical and maximum independent sets of a graph”, Discrete Applied Mathematics, Vol: 247, pp:127-134, 2018.
  • Karci, A., Karci, Ş.,”Determination of Effective Nodes in Graphs”, International Conference on Science, Engineering & Technology, Mecca, Saudi Arabia, pp:25-28, 2020.
  • Laflamme, C., Aranda, A., Soukup, D.T., Woodrow, R.,”Balanced independent sets in graphs omitting large cliques”, Journal of Combinatorial Theory, Series B, Vol:137, pp:1-9, 2019.
  • Lin, M.-S.,”Counting independent sets and maximal independent sets in some subclasses of bipartite graphs”, Discrete Applied Mathematics, Vol:251, pp:236-244, 2018a.
  • Lin. M.-S., “Simple linear-time algorithms for counting independent sets in distance-hereditary graphs”, Discrete Applied Mathematics, Vol: 239, pp:144-153, 2018b.
  • Lin, M.-S., Chen, C.-M.,”Linear-time algorithms for counting independent sets in bipartite permutation graphs”, Information Processing Letters, Vol:122, pp:1-7, 2017.
  • Marti-Farre, J., Mora, M., Ruiz, J. L.,”Uniform Clutters and Dominating Sets of Graphs”, Discrete Applied Mathematics, Vol:263, pp:220-233, 2019.
  • Naude, K.A.,”Refined pivot selection for maximal clique enumeration in graphs”, Theoretical Computer Science, vol:613, pp:28-37, 2016. Oh, S., “Maximal independent sets on a grid graph”, Discrete Mathematics, Vol:340, pp:2762-2768, 2017.
  • Peramau, G., Perkins, W.,”Counting independent sets in cubic graphs of given girth”, Journal of Combinatorial Theory, Series B, Vol:133, pp:2018.
  • Rooij, J.van, Bodlaender, H.L., “Exact algorithms for dominating set”, Discrete Applied Mathematics, Vol:159, pp:2147-2164, 2011.
  • Sah, A., Sawhhney, M., Stoner, D., Zhao, Y.,”The number of independent sets in an irregular graph”, Journal of Combinatorial Theory, Series B, Vol:138, pp:172-195, 2019.
  • Thulasiraman, K.KT., Arumugan, S., Brandstadt, A., Nishizeki, T., “Handbook of Graph Theory, Combinatorial Optimization and Algorithms”, CRC Press, Sendai, Japan, 2016.
  • Wan, P., Tu, J., Zhang, S., Li, B., “Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth”, Applied Mathematics and Computation, Vol:332, pp:42-47, 2018.
  • Wan, P., Chen, X., Tu, J., Dehmer, M., Zhang, S., Emmert-Streib, F.,”On graph entropy measures based on the number of independent sets and matchings”, Information Sciences, Vol:516, pp:491-504, 2020.
  • Yu,T., Liu, M.,”a linear time algorithm for maximal clique enumeration in large sparse graphs”, Information Processing Letters, vol:125, pp:35-40, 2017.
There are 22 citations in total.

Details

Primary Language English
Subjects Computer Software
Journal Section PAPERS
Authors

Ali Karci

Publication Date December 1, 2020
Submission Date April 7, 2020
Acceptance Date April 16, 2020
Published in Issue Year 2020 Volume: 5 Issue: 2

Cite

APA Karci, A. (2020). Finding Innovative and Efficient Solutions to NP-Hard and NP-Complete Problems in Graph Theory. Computer Science, 5(2), 137-143.

The Creative Commons Attribution 4.0 International License 88x31.png is applied to all research papers published by JCS and

A Digital Object Identifier (DOI) Logo_TM.png is assigned for each published paper