Displaying similar documents to “Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs”

Complexity theoretical results on nondeterministic graph-driven read-once branching programs

Beate Bollig (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model M is the test whether a given BP is really a BP of model M . Here it is proved that the consistency...

Cutwidth of iterated caterpillars

Lan Lin, Yixun Lin (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The cutwidth is an important graph-invariant in circuit layout designs. The cutwidth of a graph is the minimum value of the maximum number of overlap edges when is embedded into a line. A caterpillar is a tree which yields a path when all its leaves are removed. An iterated caterpillar is a tree which yields a caterpillar when all its leaves are removed. In this paper we present an exact formula for the cutwidth of the iterated caterpillars.

Finding -partitions efficiently

Simone Dantas, Celina M.H. de Figueiredo, Sylvain Gravier, Sulamita Klein (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the concept of an -partition of the vertex set of a graph , which includes all vertex partitioning problems into four parts which we require to be nonempty with only external constraints according to the structure of a model graph , with the exception of two cases, one that has already been classified as polynomial, and the other one remains unclassified. In the context of more general vertex-partition problems, the problems addressed in this paper have these properties: non-list,...

Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs

Henrik Brosenne, Matthias Homeister, Stephan Waack (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear...

A Theoretical Model for Testing New Product Sales Velocity at Small Format Retail Stores

Hiroaki Sandoh, Roy Larke (2010)

RAIRO - Operations Research

Similarity:

The present study proposes a theoretical model to test sales velocity for new products introduced in small format retail stores. The model is designed to distinguish fast moving products within a relatively short period. Under the proposed model, the sales of a newly introduced product are monitored for a prespecified period , , one week, and if the number of items sold over is equal to a prespecified integer or more, the product is considered a fast moving product and is carried...