Publication Details
Title: On Valve Adjustments that Interrupt all s-t-Paths in a Digraph
Author: U. Huckenbeck
Group: ICSI Technical Reports
Date: December 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-081.pdf
Overview:
(Pages: 15) When searching a path in a digraph, usually the following situation is given: Every node v may be entered by an arbitrary incoming arc (u,v), and v may be left by an arbitrary outgoing arc (v,w). In this paper, however, we consider graphs with valve nodes, which cannot arbitrarily be entered and left. More precisely, a movable valve is installed in each valve node v. entering v via (u,v) and leaving it via (v,w) is only possible if the current position of the valve generates a connection between these two arcs; if, however, the current valve adjustment interrupts this connection then every path using the arcs (u,v) and (v,w) is interrupted, too. We investigate the complexity of the following problem: -Given a digraph with valve nodes. Let s and t be two nodes of this graph. -Does there exist a valve adjustment that interrupts all paths from s to t? We show that this problem can be solved in deterministic polynomial time if all valve nodes belong to a particular class of valves; otherwise the problem is NP-complete.
Bibliographic Information:
ICSI Technical Report TR-93-081
Bibliographic Reference:
U. Huckenbeck. On Valve Adjustments that Interrupt all s-t-Paths in a Digraph. ICSI Technical Report TR-93-081, December 1993
Author: U. Huckenbeck
Group: ICSI Technical Reports
Date: December 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-081.pdf
Overview:
(Pages: 15) When searching a path in a digraph, usually the following situation is given: Every node v may be entered by an arbitrary incoming arc (u,v), and v may be left by an arbitrary outgoing arc (v,w). In this paper, however, we consider graphs with valve nodes, which cannot arbitrarily be entered and left. More precisely, a movable valve is installed in each valve node v. entering v via (u,v) and leaving it via (v,w) is only possible if the current position of the valve generates a connection between these two arcs; if, however, the current valve adjustment interrupts this connection then every path using the arcs (u,v) and (v,w) is interrupted, too. We investigate the complexity of the following problem: -Given a digraph with valve nodes. Let s and t be two nodes of this graph. -Does there exist a valve adjustment that interrupts all paths from s to t? We show that this problem can be solved in deterministic polynomial time if all valve nodes belong to a particular class of valves; otherwise the problem is NP-complete.
Bibliographic Information:
ICSI Technical Report TR-93-081
Bibliographic Reference:
U. Huckenbeck. On Valve Adjustments that Interrupt all s-t-Paths in a Digraph. ICSI Technical Report TR-93-081, December 1993