Approximation algorithms for connected k-edge partition

DOI10.1016/J.DAM.2026.08.023MaRDI QIDQ7353754zbMATH OpenFDO

Authors Toshimasa Ishii

Publication date 18 September 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2026.08.023

Mathematics Subject Classification ID

Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites work

• (Almost) Tight bounds and existence theorems for single-commodity confluent flows
• A homology theory for spanning tress of a graph
• A linear algorithm for bipartition of biconnected graphs
• Computing an st-numbering
• Edge-orders
• Efficient algorithms for a mixed \(k\)-partition problem of graphs without specifying bases
• Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs
• Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs
• scientific article; zbMATH DE number 3603293 (Why is no real title available?)
• scientific article; zbMATH DE number 7768372 (Why is no real title available?)
• Local search algorithms for political districting
• Most uniform path partitioning and its use in image processing
• On the complexity of partitioning graphs into connected subgraphs
• Spanning tree congestion and computation of generalized Győri-Lovász partition

This page was built for publication: Approximation algorithms for connected \(k\)-edge partition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7353754)