nach oben

Journal of Combinatorial Optimization

Erschienen in:

15.05.2019

Tropical paths in vertex-colored graphs

verfasst von: Johanne Cohen, Giuseppe F. Italiano, Yannis Manoussakis, Nguyen Kim Thang, Hong Phong Pham

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2021

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the initial graph. In this work we study the problem of finding tropical paths in vertex-colored graphs. There are two versions for this problem: the shortest tropical path problem (STPP), i.e., finding a tropical path with the minimum total weight, and the maximum tropical path problem (MTPP), i.e., finding a path with the maximum number of colors possible. We show that both versions of this problems are NP-hard for directed acyclic graphs, cactus graphs and interval graphs. Moreover, we also provide a fixed parameter algorithm for STPP in general graphs and several polynomial-time algorithms for MTPP in specific graphs, including bipartite chain graphs, threshold graphs, trees, block graphs, and proper interval graphs.

Vorheriger Artikel The one-cop-moves game on planar graphs

Nächster Artikel Algorithms for the metric ring star problem with fixed edge-cost ratio

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

Akbari S, Liaghat V, Nikzad A (2011) Colorful paths in vertex coloring of graphs. Electron J Comb 18(1):P17MathSciNetCrossRef

Angles d’Auriac JA, Bujtás C, El Maftouhi H, Narayanan N, Rosaz L, Thapper J, Tuza Z (2016) Tropical dominating sets in vertex-coloured graphs. In: Proceedings of 10th workshop on algorithms and computation (WALCOM), vol 9627, p 17

Bertossi AA (1983) Finding hamiltonian circuits in proper interval graphs. Inf Process Lett 17(2):97–101MathSciNetCrossRef

Bruckner S, Hüffner F, Komusiewicz C, Niedermeier R (2013) Evaluation of ilp-based approaches for partitioning into colorful components. In: International symposium on experimental algorithms, pp 176–187

Cohen J, Manoussakis Y, Pham H, Tuza Z (2017 (to appear)) Tropical matchings in vertex-colored graphs. In: Latin and American algorithms, graphs and optimization symposium

Corel E, Pitschi F, Morgenstern B (2010) A min-cut algorithm for the consistency problem in multiple sequence alignment. Bioinformatics 26(8):1015–1021CrossRef

Fellows MR, Fertin G, Hermelin D, Vialette S (2011) Upper and lower bounds for finding connected motifs in vertex-colored graphs. J Comput Syst Sci 77(4):799–811MathSciNetCrossRef

Foucaud F, Harutyunyan A, Hell P, Legay S, Manoussakis Y, Naserasr R (2017) Tropical homomorphisms in vertex-coloured graphs. Discret Appl Math 229:64–81CrossRef

Håstad J (2001) Some optimal inapproximability results. J ACM (JACM) 48(4):798–859MathSciNetCrossRef

Ioannidou K, Mertzios GB, Nikolopoulos SD (2009) The longest path problem is polynomial on interval graphs. In: Symposium on mathematical foundations of computer science (MFCS), vol 5734, pp 403–414

Karger D, Motwani R, Ramkumar G (1997) On approximating the longest path in a graph. Algorithmica 18(1):82–98MathSciNetCrossRef

Li H (2001) A generalization of the gallai-roy theorem. Gr Comb 17(4):681–685MathSciNetCrossRef

Lin C (2007) Simple proofs of results on paths representing all colors in proper vertex-colorings. Gr Comb 23(2):201–203MathSciNetCrossRef

Marx D (2004) Graph colouring problems and their applications in scheduling. Periodica Polytech Electr Eng 48(1–2):11–16

Micali S, Vazirani VV (1980) An \({O}(\sqrt{|V|} |{E}|)\) algorithm for finding maximum matching in general graphs. In: Proceedings of 21st symposium on foundations of computer science, pp 17–27

Uehara R, Uno Y (2004) Efficient algorithms for the longest path problem. In: International symposium on algorithms and computation, pp 871–883

Uehara R, Valiente G (2007) Linear structure of bipartite permutation graphs and the longest path problem. Inf Process Lett 103(2):71–77MathSciNetCrossRef

Titel: Tropical paths in vertex-colored graphs
verfasst von: Johanne Cohen
Giuseppe F. Italiano
Yannis Manoussakis
Nguyen Kim Thang
Hong Phong Pham
Publikationsdatum: 15.05.2019
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2021
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00416-y

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 3/2021

A spectral partitioning algorithm for maximum directed cut problem

Conflict-free connection of trees

On the complexity and approximability of repair position selection problem

Mixed connectivity properties of random graphs and some special graphs

The spectral radius and domination number in linear uniform hypergraphs

Big data driven urban railway planning: Shenzhen metro case study