| Summary: | Consider a graph <i>G</i> which belongs to a graph class <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">C</mi></semantics></math></inline-formula>. We are interested in connecting a node <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>w</mi><mo>∉</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> to <i>G</i> by a single edge <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>u</mi><mi>w</mi></mrow></semantics></math></inline-formula> where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>u</mi><mo>∈</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>; we call such an edge a tail. As the graph resulting from <i>G</i> after the addition of the tail, denoted <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>+</mo><mi>u</mi><mi>w</mi></mrow></semantics></math></inline-formula>, need not belong to the class <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">C</mi></semantics></math></inline-formula>, we want to compute the number of non-edges of <i>G</i> in a minimum <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">C</mi></semantics></math></inline-formula>-completion of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>+</mo><mi>u</mi><mi>w</mi></mrow></semantics></math></inline-formula>, i.e., the minimum number of non-edges (excluding the tail <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>u</mi><mi>w</mi></mrow></semantics></math></inline-formula>) to be added to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>+</mo><mi>u</mi><mi>w</mi></mrow></semantics></math></inline-formula> so that the resulting graph belongs to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">C</mi></semantics></math></inline-formula>. In this paper, we study this problem for the classes of split, quasi-threshold, threshold and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>P</mi><mn>4</mn></msub></semantics></math></inline-formula>-sparse graphs and we present linear-time algorithms by exploiting the structure of split graphs and the tree representation of quasi-threshold, threshold and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>P</mi><mn>4</mn></msub></semantics></math></inline-formula>-sparse graphs.
|
|---|