Linear Time Split Decomposition Revisited

2009/02/10 by Pierre Charbit, Charbit, Pierre, Fabien de Montgolfier +3 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2 #cs.DM #cs.DS #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.0902.1700

18 pages, submitted

openalex publication_date 2009/02/10 · arxiv created 2010/06/28 · arxiv updated 2010/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a family 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 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.

Cited by

• The Parameter Report: An Orientation Guide for Data-Driven Parameterization

Related

• Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
• Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems
• Practical and Efficient Split Decomposition via Graph-Labelled Trees
• Efficiently Partitioning the Edges of a 1-Planar Graph into a Planar Graph and a Forest
• Linear Time Recognition of Equimatchable Split Graphs