Decomposing weighted digraphs into sums of chains
type: Item
instance of: scholarly article
title: Decomposing weighted digraphs into sums of chains
zbMATH Open document ID: 0606.05028
DOI: 10.1016/0166-218X(87)90060-6
author: Peter Fishburn
published in: Discrete Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: Let \(W=[W_{ij}]\) denote an \(n\times n\) matrix of non-negative integers such that \(W_{ii}=0\) for all i and \(W_{ij}+W_{ji}=m\) for all distinct i and j. When does there exist a set of m rankings of n objects such that object i is ranked ahead of object j in precisely \(W_{ij}\) rankings? The author gives conditions that are necessary and sufficient for this to be the case if \(m\leq 2\) or \(n\leq 5\).
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 91B14
zbMATH DE Number: 3979086
zbMATH Keywords: rankings
zbMATH Keywords: transitive tournaments
zbMATH Keywords: chains
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: Decomposing partial orderings into chains
cites work: A decomposition theorem for partially ordered sets
cites work: Partially Ordered Sets
cites work: Q3705264
cites work: Q5598296
cites work: Q3964626
cites work: Inequalities in Dimension Theory for Posets
cites work: The Complexity of the Partial Order Dimension Problem
full work available at URL: 0166-218x(87)90060-6
OpenAlex ID: W1966172902
Recommended article: Decomposing Weighted Graphs
Recommended article: Chain decompositions of graphs
Recommended article: Decomposition of Graphs into Chains
Recommended article: Q5462155
Recommended article: Decompositions of digraphs into paths and cycles
Recommended article: Q4820835
Recommended article: Q4292032
Recommended article: Q3998644
Recommended article: Q4614846
Recommended article: Q5715093
description: scientific article; zbMATH DE number 3979086