Colorful path detection in vertex-colored temporal

Riccardo Dondi and Mohammad Mehdi Hosseinzadeh

Network Science, 2023, vol. 11, issue 4, 615-631

Abstract: Finding paths is a fundamental problem in graph theory and algorithm design due to its many applications. Recently, this problem has been considered on temporal graphs, where edges may change over a discrete time domain. The analysis of graphs has also taken into account the relevance of vertex properties, modeled by assigning to vertices labels or colors. In this work, we deal with a problem that, given a static or temporal graph, whose vertices are colored graph looks for a path such that (1) the vertices of the path have distinct colors and (2) that path includes the maximum number of colors. We analyze the approximation complexity of the problem on static and temporal graphs, and we prove an inapproximability bound. Then, we consider the problem on temporal graphs, and we design a heuristic for it. We present an experimental evaluation of our heuristic, both on synthetic and real-world graphs. The experimental results show that for many instances of the problem, our method is able to return near-optimal solutions.

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.cambridge.org/core/product/identifier/ ... type/journal_article link to article abstract page (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cup:netsci:v:11:y:2023:i:4:p:615-631_4

Access Statistics for this article

More articles in Network Science from Cambridge University Press Cambridge University Press, UPH, Shaftesbury Road, Cambridge CB2 8BS UK.
Bibliographic data for series maintained by Kirk Stebbing ().