A Constructive Arboricity Approximation Scheme

DOI10.1007/978-3-030-38919-2_5zbMath1440.68182arXiv1811.06803OpenAlexW3003623822MaRDI QIDQ3297754

Markus Blumenstock, Frank Fischer

Publication date: 20 July 2020

Published in: SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.06803

zbMATH Keywords

approximation algorithmsmatroid partitioning

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (4)

Single-pass streaming algorithms to partition graphs into few forests ⋮ Improved dynamic colouring of sparse graphs ⋮ Fast algorithms via dynamic-oracle matroids ⋮ Fully dynamic arboricity maintenance

Cites Work

• Unnamed Item
• Unnamed Item
• Fast approximation for computing the fractional arboricity and extraction of communities of a graph
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Forests, frames, and games: Algorithms for matroid sums and applications
• Arboricity and bipartite subgraph listing algorithms
• Efficient computation of implicit representations of sparse graphs
• Tight approximation bounds for dominating set on graphs of bounded arboricity
• A data structure for dynamic trees
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
• Arboricity and Subgraph Listing Algorithms
• Smallest-last ordering and clustering and graph coloring algorithms
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• Network Flow and Testing Graph Connectivity
• Algorithms for Graphic Polymatroids and Parametrics-Sets
• Fast Algorithms for Pseudoarboricity
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• Egalitarian Graph Orientations
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
• Minimum partition of a matroid into independent subsets
• Decomposition of Finite Graphs Into Forests

This page was built for publication: A Constructive Arboricity Approximation Scheme