Optimal augmentation for bipartite componentwise biconnectivity in linear time

Tsan Sheng Hsu; Ming-Yang Kao

doi:10.1137/S0895480196303216

Optimal augmentation for bipartite componentwise biconnectivity in linear time

Tsan Sheng Hsu^*, Ming-Yang Kao

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	345-362
Number of pages	18
Journal	SIAM Journal on Discrete Mathematics
Volume	19
Issue number	2
DOIs	https://doi.org/10.1137/S0895480196303216
State	Published - 2005

Keywords

Biconnectivity
Bipartite graph augmentation
Data security

ASJC Scopus subject areas

Mathematics(all)

Access to Document

10.1137/S0895480196303216

Cite this

@article{45cff152501a47f284f5b5e71df0601a,

title = "Optimal augmentation for bipartite componentwise biconnectivity in linear time",

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.",

keywords = "Biconnectivity, Bipartite graph augmentation, Data security",

author = "Hsu, {Tsan Sheng} and Ming-Yang Kao",

year = "2005",

doi = "10.1137/S0895480196303216",

language = "English (US)",

volume = "19",

pages = "345--362",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Optimal augmentation for bipartite componentwise biconnectivity in linear time

AU - Hsu, Tsan Sheng

AU - Kao, Ming-Yang

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

KW - Biconnectivity

KW - Bipartite graph augmentation

KW - Data security

UR - http://www.scopus.com/inward/record.url?scp=33646850884&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646850884&partnerID=8YFLogxK

U2 - 10.1137/S0895480196303216

DO - 10.1137/S0895480196303216

M3 - Article

AN - SCOPUS:33646850884

SN - 0895-4801

VL - 19

SP - 345

EP - 362

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -

Optimal augmentation for bipartite componentwise biconnectivity in linear time

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this