Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Combinatorial Optimization
Published in: Journal of Combinatorial Optimization 1/2020

09-04-2020

A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree

Authors: Anuj Rawat, Mark Shayman

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

Log in

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

search-config
loading …

Abstract

A rooted tree \(\mathbf {R}\) is a rooted subtree of a tree T if the tree obtained by replacing the directed edges of \(\mathbf {R}\) by undirected edges is a subtree of T. We study the problem of assigning minimum number of colors to a given set of rooted subtrees \({\mathcal {R}}\) of a given tree T such that if any two rooted subtrees share a directed edge, then they are assigned different colors. The problem is NP hard even in the case when the degree of T is restricted to at most 3 (Erlebach and Jansen, in: Proceedings of the 30th Hawaii international conference on system sciences, p 221, 1997). We present a \(\frac{5}{2}\)-approximation algorithm for this problem. The motivation for studying this problem stems from the problem of assigning wavelengths to multicast traffic requests in all-optical WDM tree networks.
previous article Fractional Gallai–Edmonds decomposition and maximal graphs on fractional matching number
next article Secure domination of honeycomb 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
Footnotes
1
For ease of exposition, in this paper we use the term set even though the object being referred to might be a multiset.
 
2
Note that this edge ordering is not unique.
 
3
It may happen that in some rounds no rooted subtrees are colored.
 
4
It may happen that both the rooted subtrees \(\mathbf {R},\mathbf {S}\) are matched to different vertices in \(M_{{\bar{G}}_{{\mathcal {P}}_{i-1}[\{u,v\}]\cup {\mathcal {Q}}_i}}\)
 
Literature
Ali M, Deogun JS (2000) Cost-effective implementation of multicasting in wavelength-routed networks. IEEE/OSA J Lightwave Technol 18(12):1628–1638CrossRef
Auletta V, Caragiannis I, Kaklamanis C, Persiano P (2000) Randomized path coloring on binary trees. In: Proceedings of the 3rd international workshop on approximation algorithms for combinatorial optimization problems, LNCS, vol 1913, pp 407–421. Springer, Berlin
Caragiannis I, Kaklamanis C, Persiano P (1997) Bounds on optical bandwidth allocation in directed fiber tree technologies. In: 2nd workshop on optics and computer science
Caragiannis I, Kaklamanis C, Persiano P (2001) Wavelength routing in all-optical tree networks: a survey. Comput Inform (Former Comput Artif Intell) 20(2):95–120MathSciNetMATH
Caragiannis I, Kaklamanis C, Persiano P (2004) Approximate path coloring with applications to wavelength assignment in WDM optical networks. In: Proceedings of the 21st international symposium on theoretical aspects of computer science, LNCS, vol 2996, pp 258–269. Springer, Berlin
Caragiannis I, Kaklamanis C, Persiano P (2006) Approximation algorithms for path coloring in trees. LNCS, vol 3484. Springer, Berlin, pp 74–96MATH
Erlebach T, Jansen K (1996) Scheduling of virtual connections in fast networks. In: Proceedings of the 4th parallel systems and algorithms workshop
Erlebach T, Jansen K (1997) Call scheduling in trees, rings and meshes. In: Proceedings of the 30th Hawaii international conference on system sciences, p 221
Erlebach T, Jansen K (2001) The complexity of path coloring and call scheduling. Theoret Comput Sci 255(1–2):33–50MathSciNetCrossRef
Gavril F (1972) Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J Comput 1(2):180–187MathSciNetCrossRef
Golumbic MC, Lipshteyn M, Stern M (1985) The edge intersection graphs of paths in a tree. J Comb Theory Ser B 38(1):8–22MathSciNetCrossRef
Golumbic MC, Lipshteyn M, Stern M (2005) Representations of edge intersection graphs of paths in a tree. In: Proceedings of the European conference on combinatorics, graph theory and applications, discrete mathematics and theoretical computer science, pp 87–92
Golumbic MC, Lipshteyn M, Stern M (2006) Finding intersection models of weakly chordal graphs. In: Proceedings of the 32nd international workshop on graph-theoretic concepts in computer science, LNCS, vol 4271, pp 241–255. Springer, Berlin
Hayward RB, Spinrad JP, Sritharan R (2007) Improved algorithms for weakly chordal graphs. ACM Trans Algorithms 3(2):14-esMathSciNetCrossRef
Jamison RE, Mulder HM (2005) Constant tolerance intersection graphs of subtrees of a tree. Discrete Math 290(1):27–46MathSciNetCrossRef
Jansen K (1997) Approximation results for wavelength routing in directed binary trees. In: 2nd Workshop on optics and computer science
Kaklamanis C, Persiano G (1996) Efficient wavelength routing on directed fiber trees. In: Proceedings of the 4th annual European symposium on algorithms, LNCS, vol 1136, pp 460–470. Springer, Berlin
Kaklamanis C, Persiano P, Erlebach T, Jansen K (1997) Constrained bipartite edge coloring with applications to wavelength routing. In: Proceedings of the 24th international colloquium on automata, languages and programming, LNCS, vol 1256, pp 493–504. Springer, Berlin
Kumar SR, Panigrahy R, Russell A, Sundaram R (1997) A note on optical routing in trees. Inf Process Lett 62(6):295–300CrossRef
Kumar V, Schwabe EJ (1997) Improved access to optical bandwidth in trees. In: Proceedings of the 8th annual ACM-SIAM symposium on discrete algorithms, pp 437–444
Laxman S, Mukherjee B (1999) Light trees: optical multicasting for improved performance in wavelength routed networks. IEEE Commun Mag 37(2):67–73CrossRef
Leon-Garcia A, Widjaja I (2000) Communication networks: fundamental concepts and key architectures. McGraw-Hill, New York
Mihail M, Kaklamanis C, Rao S (1995) Efficient access to optical bandwidth. In: Proceedings of the 36th annual symposium on foundations of computer science, p 548
Raghavan P, Upfal E (1994) Efficient routing in all-optical networks. In: Proceedings of the 26th annual ACM symposium on theory of computing, pp 134–143
Metadata
Title
A -approximation algorithm for coloring rooted subtrees of a degree 3 tree
Authors
Anuj Rawat
Mark Shayman
Publication date
09-04-2020
Publisher
Springer US
Published in
Journal of Combinatorial Optimization / Issue 1/2020
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-020-00564-6

Other articles of this Issue 1/2020

Journal of Combinatorial Optimization 1/2020 Go to the issue

OriginalPaper

An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown

OriginalPaper

Joint chance constrained shortest path problem with Copula theory

OriginalPaper

Secure domination of honeycomb networks

OriginalPaper

Planar graphs without 4- and 6-cycles are (7 : 2)-colorable

OriginalPaper

Fractional Gallai–Edmonds decomposition and maximal graphs on fractional matching number

OriginalPaper

KATZ centrality with biogeography-based optimization for influence maximization problem

Premium Partner

    Image Credits