1995 | ReviewPaper | Buchkapitel
Efficient algorithms for a mixed k-partition problem of graphs without specifying bases
verfasst von : Koichi Wada, Akinari Takaki, Kimio Kawaguchi
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper describes efficient algorithms for partitioning a k-edge-connected graph into k edge-disjoint connected subgraphs, each of which has a specified number of elements(vertices and edges). If each subgraph contains the specified element (called base), we call this problem the mixed k-partition problem with bases(called k-PART-WB), otherwise we call it the mixed k-partition problem without bases (called k-PART-WOB). In this paper, we show that k-PART-WB always has a solution for every k-edge-connected graph and we consider the problem without bases and we obtain the following results: (1)for any k≥2, k-PART-WOB can be solved in O(∥V∥√∥V∥log2∥V∥+∥E∥) time for every 4-edge-connected graph G=(V,E), (2)3-PART-WOB can be solved in O(∥V∥2) for every 2-edge-connected graph G=(V,E) and (3)4-PART-WOB can be solved in O(∥E∥2) for every 3-edge-connected graph G=(V,E).