✦ LIBER ✦

A characterization of the minimum cycle mean in a digraph

✍ Scribed by Richard M. Karp

Publisher: Elsevier Science
Year: 1978
Tongue: English
Weight: 315 KB
Volume: 23
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(78)90011-0

No coin nor oath required. For personal study only.

✦ Synopsis

Let C = (V, E) be a digraph wl,th n vertices. Let f be a function from E illto the real numbem, associating with each edg~t: e EE a weight f(e). Given any sequence of edges 0 = el, e2, , . . , ep define w(a), the wei@ of a, as CyS 1 f(q), and define m(o), the mean weight of u, as w(a)&. Let A* ==min, m(C) where C ranges over all directed cycles in G; A* is called l the mhimum cycle mean. We give a knple characterization of A*, as well as an algorithm for computing it efficiently.

📜 SIMILAR VOLUMES

The Cycle-Path Indicator Polynomial of a

The Cycle-Path Indicator Polynomial of a Digraph

✍ Ottavio M. D'Antona; Emanuele Munarini 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 126 KB

A cycle-path cover of a digraph D is a spanning subgraph made of disjoint cycles and paths. In order to count such covers by types we introduce the cyclepath indicator polynomial of D. We show that this polynomial can be obtained by a deletion-contraction recurrence relation. Then we study some spec

The Path-Cycle Symmetric Function of a D

The Path-Cycle Symmetric Function of a Digraph

✍ Timothy Y. Chow 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 885 KB

## Introduction Recently, Stanley [21] has defined a symmetric function generalization of the chromatic polynomial of a graph. Independently, Chung and Graham have defined a digraph polynomial called the cover polynomial which is closely related to the chromatic polynomial of a graph (in fact, as

Optimum tearing in large scale systems a

Optimum tearing in large scale systems and minimum feedback cutsets of a digraph

✍ Kabekode V.S. Bhat; Bharat Kinariwala 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 822 KB

In this paper we consider the problem of finding a minimum number of nonzero elements of a given n x n matrix on removal of which the resulting matrix can be permuted to an n x n lower triangular matrix using symmetric permutations on the rows and columns of the matrix. The problem is related to fin

Covering the vertices of a digraph by cy

Covering the vertices of a digraph by cycles of prescribed length

✍ D. Amar; A. Raspaud 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 427 KB

the vertices of a digraph by cycles of prescribed length, Discrete Mathematics 87 (

A Minimum on the Mean Number of Steps Ta

A Minimum on the Mean Number of Steps Taken in Adaptive Walks

✍ H.ALLEN ORR 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 138 KB

I consider the adaptation of a DNA sequence when mutant fitnesses are drawn randomly from a probability distribution. I focus on "gradient" adaptation in which the population jumps to the best mutant sequence available at each substitution. Given a random starting point, I derive the distribution of

On the existence of a specified cycle in

On the existence of a specified cycle in digraphs with constraints on degrees

✍ Abdelhamid Benhocine 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 326 KB 👁 1 views

We prove that Woodall's and GhouileHouri's conditions on degrees which ensure that a digraph is Hamiltonian, also ensure that it contains the analog of a directed Hamiltonian cycle but with one edge pointing the wrong way; that is, it contains two vertices that are connected in the same direction by