๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Realization of Matrices and Directed Graphs

โœ Scribed by Rajeev Motwani

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
182 KB
Volume
27
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis

We consider the problem of constructing a matrix with prescribed row and ร„ 4 column sums, subject to the condition that the off-diagonal entries are in 0, 1 and the diagonal entries are nonnegative integers. The pair of row and column sum vectors is called realizable if such a matrix exists. This is related to the problem of constructing a directed graph with a given degree sequence. We provide a charac-ลฝ . terization of vectors A, B which are realizable, and thereby obtain an optimal algorithm for constructing such a matrix when possible. We also point out an application of this algorithm to the heuristic solution of network flow problems.

๐Ÿ“œ SIMILAR VOLUMES

Biclique graphs and biclique matrices
Biclique graphs and biclique matrices
โœ Marina Groshaus; Jayme L. Szwarcfiter ๐Ÿ“‚ Article ๐Ÿ“… 2010 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 203 KB

## Abstract A biclique of a graph __G__ is a maximal induced complete bipartite subgraph of __G__. Given a graph __G__, the biclique matrix of __G__ is a {0,1,โˆ’1} matrix having one row for each biclique and one column for each vertex of __G__, and such that a pair of 1, โˆ’1 entries in a same row cor

Directed hamiltonian graphs
Directed hamiltonian graphs
โœ Yannis Manoussakis ๐Ÿ“‚ Article ๐Ÿ“… 1992 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 386 KB

## Abstract We give a new condition involving degrees sufficient for a digraph to be hamiltonian.

The Isomorphism Problem For Directed Pat
The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
โœ L. Babel; I.N. Ponomarenko; G. Tinhofer ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 237 KB

This paper deals with the isomorphism problem of directed path graphs and rooted directed path graphs. Both graph classes belong to the class of chordal graphs, and for both classes the relative complexity of the isomorphism problem is yet unknown. We prove that deciding isomorphism of directed path