License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.62
URN: urn:nbn:de:0030-drops-64747
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6474/
Go to the corresponding LIPIcs Volume Portal

Kupferman, Orna ; Vardi, Gal

Eulerian Paths with Regular Constraints

pdf-format:
LIPIcs-MFCS-2016-62.pdf (0.5 MB)

Abstract

Labeled graphs, in which edges are labeled by letters from some alphabet Sigma, are extensively used to model many types of
relations associated with actions, costs, owners, or other
properties. Each path in a labeled graph induces a word in Sigma^*
-- the one obtained by concatenating the letters along the edges in
the path. Classical graph-theory problems give rise to new problems
that take these words into account. We introduce and study the
constrained Eulerian path problem. The input to the problem is a
Sigma-labeled graph G and a specification L \subseteq Sigma^*.
The goal is to find an Eulerian path in G that satisfies L. We
consider several classes of the problem, defined by the classes of G
and L. We focus on the case L is regular and show that while the
problem is in general NP-complete, even for very simple graphs and
specifications, there are classes that can be solved efficiently. Our
results extend work on Eulerian paths with edge-order constraints. We
also study the constrained Chinese postman problem, where
edges have costs and the goal is to find a cheapest path that contains
each edge at least once and satisfies the specification. Finally, we
define and study the Eulerian language of a graph, namely the
set of words along its Eulerian paths.

BibTeX - Entry

@InProceedings{kupferman_et_al:LIPIcs:2016:6474,
  author =	{Orna Kupferman and Gal Vardi},
  title =	{{Eulerian Paths with Regular Constraints}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6474},
  URN =		{urn:nbn:de:0030-drops-64747},
  doi =		{10.4230/LIPIcs.MFCS.2016.62},
  annote =	{Keywords: Eulerian paths, regular languages}
}

Keywords: Eulerian paths, regular languages
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI