Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3 (Q1018104)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
scientific article

    Statements

    Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3 (English)
    0 references
    0 references
    0 references
    13 May 2009
    0 references
    Let \(G=(V,E)\) be a graph. Then a partition \(\mathcal V=(V_1,V_2)\) of \( V\) is a cut of \(G\) and the number of edges \(\{v_1,v_2\}\in E\) with \(v_i\in V_i\) for \(i=1,2\) is the size of \(\mathcal V\). Let \(mc(G)\) be the maximum size over cuts of \(G\). It is well known that it is NP-hard to construct a cut of size \(mc(G)\) also for subcubic graphs (a graph is subcubic if every vertex has degree at most \(3\)). The paper presents an algorithm constructing, for a given subcubic graph \(G\), a cut of \(G\) of size greater than \(\frac 56\,mc(G)\). The algorithm is based on a special decomposition of a graph into subgraphs depending on cycles. The authors give an example of a non-subcubic graph which has no such decomposition. A comparison of this algorithm with similar algorithms is presented.
    0 references
    maximum cut
    0 references
    cubic graph
    0 references
    approximation algorithm
    0 references
    unicyclic graph
    0 references
    vertex decomposition
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references