Optimal augmentation for bipartite componentwise biconnectivity in linear time

Tsan Sheng Hsu*, Ming-Yang Kao

*Corresponding author for this work

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

A graph is componentwise biconnected if every connected component either is an isolated vertex or is biconnected. We present a linear-time algorithm for the problem of adding the smallest number of edges to make a bipartite graph componentwise biconnected while preserving its bipartiteness. This algorithm has immediate applications for protecting sensitive information in statistical tables.

Original languageEnglish (US)
Pages (from-to)345-362
Number of pages18
JournalSIAM Journal on Discrete Mathematics
Volume19
Issue number2
DOIs
StatePublished - Dec 1 2005

Keywords

  • Biconnectivity
  • Bipartite graph augmentation
  • Data security

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Optimal augmentation for bipartite componentwise biconnectivity in linear time'. Together they form a unique fingerprint.

  • Cite this