Back to Search
Start Over
Parametric bisubmodular function minimization and its associated signed ring family
- Source :
- Discrete Applied Mathematics. 227:142-148
- Publication Year :
- 2017
- Publisher :
- Elsevier BV, 2017.
-
Abstract
- The present paper shows an extension of the theory of principal partitions for submodular functions to that for bisubmodular functions. We examine the structure of the collection of all solutions of a parametric minimization problem described by a bisubmodular function and two vectors. The bisubmodular function to be minimized for each parameter is the sum of the bisubmodular function and a parameterized box-bisubmodular function given in terms of the two vectors. We show that the collection of all the minimizers for all parameters forms a signed ring family and it thus induces a signed poset on a signed partition of the underlying set. We further examine the structure of the signed ring family and reveal the decomposition structure depending on critical values of the parameter. Moreover, we discuss the relation between the results of this paper on bisubmodular functions and the theory of principal partitions developed for submodular functions.
- Subjects :
- Discrete mathematics
021103 operations research
Signed poset
Applied Mathematics
Minimization problem
0211 other engineering and technologies
Parameterized complexity
Function minimization
Principal partition
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Submodular set function
Combinatorics
Computer Science::Discrete Mathematics
010201 computation theory & mathematics
Discrete Mathematics and Combinatorics
Partition (number theory)
Partially ordered set
Bisubmodular function
Signed ring family
Parametric statistics
Mathematics
Subjects
Details
- ISSN :
- 0166218X
- Volume :
- 227
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics
- Accession number :
- edsair.doi.dedup.....727e94daead0e2a29bfd6595a1799130