nach oben

Journal of Combinatorial Optimization

Erschienen in:

23.07.2015

Lower bounds for positive semidefinite zero forcing and their applications

verfasst von: Boting Yang

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Benders decomposition for set covering problems

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

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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

Titel: Lower bounds for positive semidefinite zero forcing and their applications
verfasst von: Boting Yang
Publikationsdatum: 23.07.2015
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2017
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9936-0

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2017

Neighbor product distinguishing total colorings

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

Code for polyomino and computer search of isospectral polyominoes

A solution to a conjecture on the generalized connectivity of graphs

On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches

On consecutive edge magic total labelings of connected bipartite graphs