6533b86efe1ef96bd12cc7bc

RESEARCH PRODUCT

A Constructive Arboricity Approximation Scheme

Markus BlumenstockFrank Fischer

subject

PseudoforestArboricityApproximation algorithm0102 computer and information sciences02 engineering and technology01 natural sciencesConstructiveCombinatoricsSet (abstract data type)Computer Science::Discrete Mathematics010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineeringGraph (abstract data type)Partition (number theory)020201 artificial intelligence & image processingMatroid partitioningComputer Science::Data Structures and AlgorithmsGeneralLiterature_REFERENCE(e.g.dictionariesencyclopediasglossaries)Computer Science::Distributed Parallel and Cluster ComputingMathematicsofComputing_DISCRETEMATHEMATICSMathematics

description

The arboricity \(\varGamma \) of a graph is the minimum number of forests its edge set can be partitioned into. Previous approximation schemes were nonconstructive, i.e., they approximate the arboricity as a value without computing a corresponding forest partition. This is because they operate on pseudoforest partitions or the dual problem of finding dense subgraphs.

yearjournalcountryeditionlanguage
2020-01-01
https://doi.org/10.1007/978-3-030-38919-2_5