article · 1999

Optimal Augmentation of a Submodular and Posi-modular Set Function by a Multigraph

Hiroshi Nagamochi, Takashi Shiraki, Toshihide Ibaraki

Cited by 0Abstract and details only

Abstract

Given a nite set V and a set function f : 2 7! Z, we consider the problem of constructing an undirected multigraph G = (V; E) such that the cut function c G : 2 7! Z of G and f together has value at least 2 for all non-empty and proper subsets of V . If f is intersecting submodular and posi-modular, and satis es the tripartite inequality, then we show that such a multigraph G with the minimum number of edges can be found in O((T f + 1)n log n) time, where n = jV j and T f is the time to compute the value of f(X) for a subset X V .

Cite this paper

APA 7

Nagamochi, H., Shiraki, T., & Ibaraki, T. (1999). Optimal Augmentation of a Submodular and Posi-modular Set Function by a Multigraph.

MLA 9

Nagamochi, Hiroshi, et al. “Optimal Augmentation of a Submodular and Posi-modular Set Function by a Multigraph.” 1999.

Chicago

Nagamochi, Hiroshi, Takashi Shiraki, and Toshihide Ibaraki. 1999. “Optimal Augmentation of a Submodular and Posi-modular Set Function by a Multigraph.”

Harvard

Nagamochi, H., Shiraki, T. and Ibaraki, T. (1999) ‘Optimal Augmentation of a Submodular and Posi-modular Set Function by a Multigraph’.

BibTeX

@article{nagamochi1999optimal,
  title = {{Optimal Augmentation of a Submodular and Posi-modular Set Function by a Multigraph}},
  author = {Nagamochi, Hiroshi and Shiraki, Takashi and Ibaraki, Toshihide},
  year = {1999}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.