Top

Journal of Combinatorial Optimization

Published in:

23-07-2015

Lower bounds for positive semidefinite zero forcing and their applications

Author: Boting Yang

Published in: Journal of Combinatorial Optimization | Issue 1/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The positive semidefinite zero forcing number of a graph is a parameter that is important in the study of minimum rank problems. In this paper, we focus on the algorithmic aspects of computing this parameter. We prove that it is NP-complete to find the positive semidefinite zero forcing number of a given graph, and this problem remains NP-complete even for graphs with maximum vertex degree 7. We present a linear time algorithm for computing the positive semidefinite zero forcing number of generalized series–parallel graphs. We introduce the constrained tree cover number and apply it to improve lower bounds for positive semidefinite zero forcing. We also give formulas for the constrained tree cover number and the tree cover number on graphs with special structures.

previous article Benders decomposition for set covering problems

next article A PTAS for minimum weighted connected vertex cover problem in 3-dimensional wireless sensor networks

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

There should not be an edge between \(a'\) and \(b'\) on the third graph in Fig. 4 of Yang (2013).

AIM Minimum Rank-Special Graphs Work Group (2008) Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl 428(7):1628–1648MathSciNetCrossRef

Barioli F, Barrett W, Fallat S, Hall HT, Hogben L, Shader B, van den Driessche P, van der Holst H (2013) Parameters related to tree-width, zero forcing, and maximum nullity of a graph. J Graph Theory 72:146–177MathSciNetCrossRefMATH

Barioli F, Barrett W, Fallat S, Hall HT, Hogben L, Shader B, van den Driessche P, van der Holst H (2010) Zero forcing parameters and minimum rank problems. Linear Algebra Appl 433(2):401–411MathSciNetCrossRefMATH

Barioli F, Fallat S, Mitchell L, Narayan S (2011) Minimum semidefinite rank of outerplanar graphs and the tree cover number. Electron J Linear Algebra 22:10–21MathSciNetCrossRefMATH

Bienstock D, Seymour P (1991) Monotonicity in graph searching. J Algorithms 12:239–245MathSciNetCrossRefMATH

Booth M, Hackney P, Harris B, Johnson CR, Lay M, Mitchell LH, Narayan SK, Pascoe A, Steinmetz K, Sutton BD, Wang W (2008) On the minimum rank among positive semidefinite matrices with a given graph. SIAM J Matrix Anal Appl 30:731–740MathSciNetCrossRefMATH

Burgarth D, Giovannetti V (2007) Full control by locally induced relaxation. Phys Rev Lett 99(10):100–501CrossRef

Duffin RJ (1965) Topology of series parallel networks. J Math Appl 10:303–318MathSciNetMATH

Dyer D, Yang B, Yaşar O (2008) On the fast searching problem. In: Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM’08), Lecture notes in Computer Science, vol 5034. Springer, New York, pp 143–154

Ekstrand J, Erickson C, Hall HT, Hay D, Hogben L, Johnson R, Kingsley N, Osborne S, Peters T, Roat J, Ross A, Row D, Warnberg N, Young M (2013) Positive semidefinite zero forcing. Linear Algebra Appl 439:1862–1874MathSciNetCrossRefMATH

Ekstrand J, Erickson C, Hay D, Hogben L, Roat J (2012) Note on positive semidefinite maximum nullity and positive semidefinite zero forcing number of partial \(2\)-trees. Electron J Linear Algebra 23:79–87MathSciNetCrossRefMATH

Fallat S, Meagher K, Yang B (2015) On the complexity of the positive semidefinite zero forcing number. Linear Algebra Appl doi:10.1016/j.laa.2015.03.011

Hopcroft J, Tarjan R (1973) Efficient algorithms for graph manipulation. Commun ACM 16(6):372–378CrossRef

Kirousis L, Papadimitriou C (1986) Searching and pebbling. Theor Comput Sci 47:205–218MathSciNetCrossRefMATH

Kratochvíl J, Tuza Z (2002) On the complexity of bicoloring clique hypergraphs of graphs. J Algorithms 45:40–54MathSciNetCrossRefMATH

Megiddo N, Hakimi S, Garey M, Johnson D, Papadimitriou C (1988) The complexity of searching a graph. J ACM 35:18–44MathSciNetCrossRefMATH

Robertson N, Seymour P (1983) Graph minors I: excluding a forest. J Comb Theor B 35:39–61MathSciNetCrossRefMATH

Robertson N, Seymour P (1984) Graph minors III: planar tree-width. J Comb Theor B 36:49–64MathSciNetCrossRefMATH

Valdes J, Tarjan RE, Lawler EL (1982) The recognition of series parallel digraphs, SIAM J Comput 11: 289–313, In: Proc. 11th ACM Symp. Theory of Computing pp 1–12, 1979

West DB (2001) Introduction to graph theory, 2nd edn. Prentice Hall, Upper Saddle River

Yang B (2013) Fast-mixed searching and related problems on graphs. Theor Comput Sci 507(7):100–113MathSciNetCrossRefMATH

Yang B (2007) Strong-mixed searching and pathwidth. J Comb Optim 13:47–59MathSciNetCrossRefMATH

Title: Lower bounds for positive semidefinite zero forcing and their applications
Author: Boting Yang
Publication date: 23-07-2015
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2017
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9936-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2017

A PTAS for minimum weighted connected vertex cover problem in 3-dimensional wireless sensor networks

Neighbor product distinguishing total colorings

Coupon coloring of some special graphs

A solution to a conjecture on the generalized connectivity of graphs

Maximal independent sets in a generalisation of caterpillar graph

A novel approach for detecting multiple rumor sources in networks with partial observations

Premium Partner