Linear Time Split Decomposition Revisited

Given a family $\mathcal{F}$ of subsets of a ground set V, its orthogonal is defined to be the family of subsets that do not overlap any element of $\mathcal{F}$. Using this tool we revisit the problem of designing a simple linear time algorithm for undirected graph split (also known as 1-join) deco...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 2012-01, Vol.26 (2), p.499-514
Main Authors: Charbit, Pierre, de Montgolfier, Fabien, Raffinot, Mathieu
Format: Article
Language:English
Subjects:
Algorithms
Computer Science
Data Structures and Algorithms
Decomposition
Graphs
Leaves
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a family $\mathcal{F}$ of subsets of a ground set V, its orthogonal is defined to be the family of subsets that do not overlap any element of $\mathcal{F}$. Using this tool we revisit the problem of designing a simple linear time algorithm for undirected graph split (also known as 1-join) decomposition. [PUBLICATION ABSTRACT]
ISSN:0895-4801
1095-7146
DOI:10.1137/10080052X