Unary Automatic Graphs: An Algorithmic Perspective

Details Unary Automatic Graphs: An Algorithmic Perspective Unary Automatic Graphs: An Algorithmic Perspective

2008-09-19

arxiv.org/abs/0809.3330v1

Mathematics

Logic

19 pages, 3 figures. Extended abstract in TAMC 2008 LNCS 4978 pp 548-559

Scientific paper

This paper studies infinite graphs produced from a natural unfolding operation applied to finite graphs. Graphs produced via such operations are of finite degree and automatic over the unary alphabet (that is, they can be described by finite automata over unary alphabet). We investigate algorithmic properties of such unfolded graphs given their finite presentations. In particular, we ask whether a given node belongs to an infinite component, whether two given nodes in the graph are reachable from one another, and whether the graph is connected. We give polynomial-time algorithms for each of these questions. For a fixed input graph, the algorithm for the first question is in constant time and the second question is decided using an automaton that recognizes the reachability relation in a uniform way. Hence, we improve on previous work, in which non-elementary or non-uniform algorithms were found.

Affiliated with

Also associated with

No associations

Rating

Unary Automatic Graphs: An Algorithmic Perspective does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Unary Automatic Graphs: An Algorithmic Perspective, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unary Automatic Graphs: An Algorithmic Perspective will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-157516