nach oben

Journal of Combinatorial Optimization

Erschienen in:

20.07.2016

Characterizations of k-cutwidth critical trees

verfasst von: Zhen-Kun Zhang, Hong-Jian Lai

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 cutwidth problem for a graph G is to embed G into a path such that the maximum number of overlap edges (i.e., the congestion) is minimized. The investigations of critical graphs and their structures are meaningful in the study of a graph-theoretic parameters. We study the structures of k-cutwidth \((k>1)\) critical trees, and use them to characterize the set of all 4-cutwidth critical trees.

Vorheriger Artikel The minimum value of geometric-arithmetic index of graphs with minimum degree 2

Nächster Artikel Newly deterministic construction of compressed sensing matrices via singular linear spaces over finite fields

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

Nur mit Berechtigung zugänglich

Bondy JA, Murty USR (2008) Graph theory. Springer, New YorkCrossRefMATH

Chung FRK, Seymour PD (1985) Graphs with small bandwidth and cutwidth. Discret Math 75:268–277MathSciNetMATH

Chung MJ, Makedon F, Sudborough IH, Turner J (1985) Polynomial time algorithms for the min cut problem on degree restricted trees. SIAM J Comput 14:158–177MathSciNetCrossRefMATH

Diaz J, Petit J, Serna M (2002) A survey of graph layout problems. ACM Comput Surv 34:313–356CrossRef

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Company, San FranciscoMATH

Korach E, Solel N (1993) Treewidth, pathwidth and cutwidth. Discret Appl Math 43:97–101CrossRefMATH

Lin Y, Yang A (2004) On 3-cutwidth critical graphs. Discret Math 275:339–346MathSciNetCrossRefMATH

Lin Y, Li X, Yang A (2002) A degree sequence method for the cutwidth problem of graphs. Appl Math J Chin Univ B 17(2):125–134MathSciNetCrossRefMATH

Lin Y (2003) The cutwidth of trees with diameter at most 4. Appl Math J Chin Univ B 18(3):361–369MathSciNetCrossRefMATH

Liu H, Yuan J (1995) Cutwidth problem on graphs. Appl Math J Chin Univ A 10(3):339–348MathSciNetMATH

Rolin J, Sykora O, Vrto I (1995) Optimal cutwidth of meshes., Lecture Notes in Computer Science. Springer, Berlin

Yannakakis M (1985) A polynomial algorithm for the min-cut arrangement of trees. J ACM 32:950–989MathSciNetCrossRefMATH

Zhang Z, Lin Y (2012) On 4-cutwidth critical trees. ARS Comb 105:149–160MathSciNetMATH

Titel: Characterizations of k-cutwidth critical trees
verfasst von: Zhen-Kun Zhang
Hong-Jian Lai
Publikationsdatum: 20.07.2016
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-016-0061-5

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

On minimally 2-connected graphs with generalized connectivity

Modified linear programming and class 0 bounds for graph pebbling

Parameterized algorithms for min–max 2-cluster editing

The thickness of the complete multipartite graphs and the join of graphs

The k-metric dimension

On zero-sum -magic graphs