Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/32123
DC FieldValueLanguage
dc.contributor.authorErlebach, Thomas-
dc.contributor.authorHoffmann, Michael-
dc.contributor.authorKammer, F.-
dc.contributor.editorSpeckmann, B.-
dc.contributor.editorKobayashi, N.-
dc.date.accessioned2015-05-07T09:24:41Z-
dc.date.available2016-06-20T01:45:07Z-
dc.date.issued2015-06-20-
dc.identifier.citationProceedings of the 42nd International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science Volume 9134, 2015, pp. 444-455 (12)en
dc.identifier.isbn978-3-662-47671-0-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/2381/32123-
dc.description.abstractA temporal graph is a graph in which the edge set can change from step to step. The temporal graph exploration problem TEXP is the problem of computing a foremost exploration schedule for a temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and has the smallest arrival time. We consider only temporal graphs that are connected at each step. For such temporal graphs with $n$ nodes, we show that it is $\NP$-hard to approximate TEXP with ratio $O(n^{1-\epsilon})$ for any $\epsilon>0$. We also provide an explicit construction of temporal graphs that require $\Theta(n^2)$ steps to be explored. We then consider TEXP under the assumption that the underlying graph (i.e. the graph that contains all edges that are present in the temporal graph in at least one step) belongs to a specific class of graphs. Among other results, we show that temporal graphs can be explored in $O(n^{1.5}k^2\log n)$ steps if the underlying graph has treewidth $k$ and in $O(n\log^3 n)$ steps if the underlying graph is a $2\times n$ grid. Finally, we show that sparse temporal graphs with regularly present edges can always be explored in $O(n)$ steps.en
dc.language.isoenen
dc.publisherSpringer Berlin Heidelberg-
dc.rightsThe final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-47672-7_36-
dc.subjectinapproximabilityen
dc.subjectplanar graphsen
dc.subjectbounded treewidthen
dc.subjectregularly present edgesen
dc.subjectirregularly present edgesen
dc.titleOn Temporal Graph Explorationen
dc.typeConference Paperen
dc.identifier.doi10.1007/978-3-662-47672-7_36-
dc.description.statusPeer-revieweden
dc.description.versionPost-printen
dc.description.presentedICALP, Kyotoen
dc.date.end2015-07-10-
dc.date.start2015-07-06-
pubs.organisational-group/Organisationen
pubs.organisational-group/Organisation/COLLEGE OF SCIENCE AND ENGINEERINGen
pubs.organisational-group/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Scienceen
dc.identifier.eisbn978-3-662-47672-7-
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat