Theory of Principal Partitions Revisited

Satoru Fujishige ()
Additional contact information
Satoru Fujishige: Kyoto University, Research Institute for Mathematical Sciences

Chapter 7 in Research Trends in Combinatorial Optimization, 2009, pp 127-162 from Springer

Abstract: Summary The theory of principal partitions of discrete systems such as graphs, matrices, matroids, and submodular systems have been developed since 1967. In the early stage of the developments during 1967–75 the principal partition was considered as a decomposition of a discrete system into its components together with a partially ordered structure of the set of the components. It then turned out that such a decomposition with a partial order on it arises from the submodularity structure pertinent to the system and it has been realized that the principal partitions are closely related to resource allocation problems with submodular structures, which are kind of dual problems. The aim of this paper is to give an overview of the developments in the theory of principal partitions and some recent extensions with special emphasis on its relation to associated resource allocation problems in order to make it better known to researchers in combinatorial optimization.

Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-76796-1_7

Ordering information: This item can be ordered from
http://www.springer.com/9783540767961

DOI: 10.1007/978-3-540-76796-1_7

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().