[PDF] CNAM 3 demande de prise en

View - Download CNAM

Previous PDF

Next PDF

Available online at www.sciencedirect.com

Computers & Operations Research 30 (2003) 1931-1944www.elsevier.com/locate/dsw An exact algorithm for the maximum leaf spanning tree problem

Tetsuya Fujie

Department of Management Science, Kobe University of Commerce, 8-2-1, Gakuen-nishimachi, Nishi-ku,

Kobe 651-2197, Japan

Received1 April 2001; receivedin revisedform 1 April 2002

Abstract

Given a connectedgraph, the Maximum Leaf Spanning Tree Problem (MLSTP) is to ?nda spanning tree whose number of leaves (degree-one vertices) is maximum. We propose a branch-and-bound algorithm for MLSTP, in which an upper boundis obtainedby solving a minimum spanning tree problem. We report computational results for randomly generatedgraphs andgridgraphs with up to 100 vertices.

Scope and purpose

There exist many applications which can be modeled using graphs. Spanning trees in a graph are often

considered since it consists of the minimal set of edges which connect each pair of vertices. The minimum

spanning tree problem is a classical and fundamental problem on graphs. In this paper, we consider the

maximum leaf spanning tree problem which is to ?nda spanning tree with the maximum number of leaves

(degree-one vertices). This problem has an application in the area of communication networks and circuit

layouts. Since the problem is NP-hard, several approximation algorithms have been considered. The purpose

of the paper is to propose a branch-and-boundalgorithm for the problem. We propose an upper boundwhich

is obtainedby solving the minimum spanning tree problem. To the author"s knowledge, this is the ?rst exact

algorithm to the problem. ?2003 Elsevier Science Ltd. All rights reserved. Keywords:Branch andbound; Spanning trees; Integer programming

Tel.: +81-78-794-6161; fax: +81-78-794-6166.

E-mail address:fujie@kobeuc.ac.jp(T. Fujie).

0305-0548/03/$-see front matter?2003 Elsevier Science Ltd. All rights reserved.

PII:S0305-0548(02)00117-X

1932T. Fujie/Computers & Operations Research 30 (2003) 1931-1944

1. Introduction

Consider a spanning tree in a given connected graphG. A vertex is calledaleafif it has exactly one incident edge in the spanning tree. In this paper, we consider the Maximum Leaf Spanning Tree Problem (MLSTP), which is to ?nda spanning tree inG, whose number of leaves is maximum. Several applications of MLSTP can be foundin the area of communication networks andcircuit layouts [1,2]. For example, let us consider the case of communication networks where the vertices correspondto terminals andthe aim is to design a tree-like layout in the network. Then, "leaf terminals" may have lighter work loads than "intermediate terminals" of degree at least two when intermediate terminals have the work on message routing. Hence, in this case, the solution of MLSTP could provide a reasonable layout. A related discussion of this model can be found in [3]. MLSTP is known to be NP-hard[4]. Moreover, it is shown that MLSTP is MAX SNP-hard[5] which implies that there exist?¿0 and?¿1 such that achieving an approximation ratio (1 +?) is NP-hardbut there is a polynomial time?-approximation algorithm. Lu andRavi [6,7] developed

3-approximation algorithms and, recently, an improved 2-approximation algorithm was developed by

Solis-Oba [8].

MLSTP is equivalent to the Minimum ConnectedDominating Set Problem (MCDSP). Here, a subset of vertices is calleda connecteddominating set if its inducedsubgraph of the subset is connectedandeach remaining vertex is adjacent to the subset, andMCDSP is to ?nda connected dominating set of maximum size. Hence a set of non-leaves of a spanning tree is a connected dominating set and, conversely, a set of vertices outside a connected dominating set is a set of leaves of some spanning tree. Though we know that MCDSP is also NP-hard, the inapproximability result is di?erent. Guha and Khuller [1] showedthat the set cover problem is reducedto MCDSP by an approximation preserving reduction. For the set cover problem ofnelements in the ground set, Feige [9] showedthat achieving an approximation ratio (1-?)lnnimplies NP hasn

O(loglogn)

deterministic algorithms for any?¿0. In this paper, we present a branch-and-bound algorithm for MLSTP. To the author"s knowledge, this is the ?rst exact algorithm for MLSTP. We use an integer programming formulation, provided in [10], which will be denoted by (P1). Fernandes and Gouveia [3] gave directed integer programming formulations by replacing each edge by two arcs with opposite directions: One of their formulations is closely relatedto (P1) (see Section2). The relaxation problem of (P1) is a minimum span- ning tree problem, andhence an upper boundis easily computable. Computational results of the branch-and-boundalgorithm will be reportedfor randomly generatedgraphs andgridgraphs with up to 100 vertices. The rest of the paper is organizedas follows. In Section2, (P1) is introducedandwe make some observations of the spanning tree problem relaxation of (P1). The branch-and-bound algorithm is described in Section3. In Section4, we report our computational results for randomly generated graphs andgridgraphs. Finally, some concluding remarks are given in Section5.

2. Formulations and upper bounds

LetG=(V;E) be a connectedgraph, whereVis a set of vertices andEa set of edges. Fori?V, let? G (i) denote a set of edges adjacent toi. For a spanning treeT=(V;E T )inG, the vertexi?V with|? T (i)|=1 is calledaleaf. We shall assume|? G (i)|¿2 fori?V: Handling degree-one vertices T. Fujie/Computers & Operations Research 30 (2003) 1931-19441933 (i?Vwith|? G (i)|= 1) will be discussed in Section3.3. For simplicity,?(i) will be usedinstead of? G (i) if the graphGis clearly understood. For a spanning treeT=(V;E T )inG, we de?ne its incidence vector? T T e |e?E)as? T e =1ife?E T T e =0 otherwise. We denote by ST G a set of all incidence vectors of spanning trees inG. Let us de?ne a weighted MLSTP. Given a non-negative weightw i fori?V, the weighedMLSTP is to ?nda spanning treeTinG, which maximizes? i?L(T) w i whereL(T) is a set of leaves of

T. The unweightedMLSTP is associatedwithw

i = 1 for alli?Vand, in the rest of the paper, we will call MLSTP as the unweightedMLSTP. A formulation of the weightedMLSTP is providedas follows: (P1) maximize? i?V w i y i (1) subject tox?ST G ;(2) x(?(i))+(|?(i)|-1)y i

6|?(i)|(i?V);(3)

y i ?{0;1}(i?V);(4) wherex=(x e |e?E) is a vector of edges andx(?(i)) =? e??(i) x e fori?V. In our formulation (P1),y i =1only ifthe vertexiis a leaf of a spanning tree representedbyx?ST G . Hence the 0-1 vectory=(y i |i?V) represents asubsetof leaves of a spanning treex?ST G . Since the weighted MLSTP is a maximization problem andthe coe?cientsw i (i?V) of the objective function (1) are non-negative, (P1) is a validformulation of the weightedMLSTP. Formulation (P1) is followedby

Fujie [10].

A relaxation problem of (P1) is obtainedby relaxing the 0-1 conditions on the variablesy i (i?V).

Since (2) and(3) implyy

i

61 fori?V, we can relax the 0-1 conditions (4) by non-negativity

constraints. Then, for any optimal solution of the relaxation problem, the constraint (3) must hold with equality. Hence, the relaxation problem is equivalent to the following problem:

P1) maximize?

i?V w i |?(i)|-x(?(i)) |?(i)|-1 i?V w i |?(i)| m?(i)|-1-? e={i;j}?E ?w i |?(i)|-1+w j |?(j)|-1? x e subject tox?ST G P1) is a minimum spanning tree problem with weightw i =(|?(i)|-1) +w j =(|?(j)|-1) on edge e={i;j}?E, andcan be solvede?ciently (see e.g. [11]). Note that (

P1) is equivalent to the

Lagrangian relaxation of (P1) with respect to the constraint (3) since this Lagrangian relaxation satis?es the Integral Property [12] (see [10]). We also note that (

P1) works well as a relaxation

problem since we have assumed|?(i)|¿2(i?V).

Here, we make some observations of relaxation (

P1). Firstly, (P1) remains a validformulation of

the weightedMLSTP even if the constraints (3) are replacedby x(?(i))+(|V|-2)y i

6|V|-1(i?V):(5)

1934T. Fujie/Computers & Operations Research 30 (2003) 1931-1944

Fig. 1. A 3-regular graph anda spanning tree (black vertex is a leaf). One of the directed integer programming formulations of Fernandes and Gouveia [3] essentially adopts (5) to relate variables of arcs andvertices. On the other hand, if we use (5) in (P1), the maximum value of ( P1) for MLSTP is equal to|V|-1, which is a trivial upper bound. Secondly, letT R be an optimal spanning tree of (P1). Then we have? i?L(TR) w i

6v(P1)6v(P1), wherev(·)

denotes the optimal solution value of problem (·). Hence, the relaxation gapv(

P1)-v(P1) satis?es

v(

P1)-v(P1)6v(P1)-?

i?L(TR) w i i?V w i |?(i)|-|? TR (i)| m?(i)|-1; whereV ={i?V|1¡|? TR (i)|¡|?(i)|}. This observation implies that, for example, if any non-leaf i??Lis full degree (i.e.|? TR (i)|=|? G (i)|),T R is optimal for the weightedMLSTP. Lastly, for MLSTP for anr-regular graphG(i.e. a graphGsatisfying|? G (i)|=rfori?V), an explicit upper boundis obtained. Namely, for any spanning treex?ST G , we have i?V r-x(?(i)) r-1=rn--1-? i?V x(?(i)) r-1=rn--1-2(n-1)r-1=(r-2)n+2r-1: For 3-regular graphs, the upper boundisn=2+1, while Storer [2] gave a lower boundofn=4+2. The upper boundis tight: In Fig.1, we show the tight example. The number of vertices in the graph is n=1+3+3(2+···+2 h )+2·3·2 h+1 =4+3·(2 h+1 -2)+2·3·2 h+1 =9·2 h+1 -2; while the number of leaves of the spanning tree is

3·2

h +3·2 h+1 =9·2 h =n=2+1:

For further results on lower bounds, see [13].

3. Algorithm

In this section, we describe a branch-and-bound algorithm based on the formulation (P1). T. Fujie/Computers & Operations Research 30 (2003) 1931-19441935

3.1. Solving subproblems

Recall our formulation (P1) of the weightedMLSTP. In this formulation, the 0-1 vectoryrep- resents a subset of leaves of the corresponding spanning treex?ST G . Hence, we can restate the weightedMLSTP as: "Findasubsetof leaves (leaf subset) of some spanning tree of the maximum weight". This restatement will help us to formulate subproblems. Let us denote a subproblem by

MLSTP(S

1 ;S 0 ;F), where (S 1 ;S 0 ;F) is a partition ofVandany vertex inS 1 must be containedin any leaf subset, none of vertex inS 0 must be containedin any leaf subset, andF=V\(S 1 ?S 0 )isaset of free vertices. The root problem is MLSTP(∅;∅;V). It can be easily shown that MLSTP(S 1 ;S 0 ;F) has a feasible solution if andonly ifG\S 1 is connectedand, fori?S 1 , there is an edge that con- nectsiandsome vertex inV\S 1 [8]. Hence, checking feasibility of MLSTP(S 1 ;S 0 ;F) can be done e?ciently.

The subproblem MLSTP(S

1 ;S 0 ;F) is formulatedas follows: (P(S 1 ;S 0 ;F)) maximize? i?F w i y i +w(S 1 subject tox?ST G x(?(i))+(|?(i)|-1)y i

6|?(i)|(i?F);

x(?(i))61(i?S 1 y i ?{0;1}(i?F); wherew(S 1 i?S1 w i . By relaxing the 0-1 constraints, we have a relaxation problem P(S 1 ;S 0 ;F)) maximize? i?F w i |?(i)| m?(i)|-1-? e?E d e x e +w(S 1quotesdbs_dbs49.pdfusesText_49

[PDF] apa udem

[PDF] apa vs iso 690

[PDF] apakah film negeri 5 menara mengandung nilai-nilai pendidikan apa saja

[PDF] apb bulletins scolaires

[PDF] apb candidat libre

[PDF] apb complementaire 2017

[PDF] apb demande de bourse 2017

[PDF] apb gestion

[PDF] apb procédure complémentaire

[PDF] apb resultats

[PDF] apc méthodologie ce1

[PDF] apc méthodologie cp

[PDF] apci code

[PDF] apicil mutuelle tableau de garantie

[PDF] aplicaciones de la sal