C Zuniga
email: catya.zuniga@unaq.edu.mx

+ D Delahaye

[EN-A-049] An Efficient Landing Route Structure to Enhance Airport capacity

Keywords: merging and sequencing problem, terminal maneuvering air traffic management, optimization, discrete event simulation

Due to the air traffic growth tendencies around the world, capacity problems have been emerging among different elements within the system, but perhaps one of the most visible and expensive is the air traffic congestion. Therefore, innovative methodologies to tackle it have been developing. Special attention has been centering at the terminal maneuvering area which is perhaps one of the most complex types of airspace. In this work, a simulationoptimization modeling technique is presented to tackle the air traffic congestion by building an optimal landing sequences to feed optimally the runway. Therefore, different Terminal Maneouver Area route structures have been designed and tested to analyze its benefits. In a first approach, Queretaro (Mexico) airspace is used as a case study. Following this, the merging and sequencing problem is addressed by means of genetic algorithms aiming to minimize conflicts between arrivals; and in a third stage, a discrete simulation approach is used to introduced the stochastic aspects of the problem such as arrival speed profiles, delays, and wind interaction, among others.

INTRODUCTION

Nowadays, Air Transport System plays a major role in the global economy. It connects businesses to global markets; it is a major tourist's transportation, more than half of the world's tourist travel by air; it also enables worldwide access to time-sensitive products, from fresh products to emergency aid. In the past 20 years, air travel has grown at an average of 1.8 times as fast as global Gross Domestic Product (GDP) even though there have been substantial yearly crisis such as Gulf crisis, 9/11 attacks or 2008 financial crisis, to mention some.

Passenger traffic grew 5.3% expressed in Revenue Passenger Kilometers (RPK) in 2012, moving around 2.9 billion passengers and $5.3 trillion USD worth of cargo. This growth has supported the employment of 56.6 million people (directly and indirectly) and contributed over $2.2 trillion USD to global GDP [START_REF] Airbus | Global Market Forecast 2015-2034[END_REF].

Traffic distribution of the largest markets during 2012 place North American, Europe and Asia-Pacific with the 83% of the total global traffic. The Asia-Pacific region has been delivering the highest margins (around the 31% of the traffic) and largest profits followed by North American, with almost the same amount of traffic load. Latin America moved 4% of the worldwide traffic load but its tendency previews an economic growth of 4% per year [START_REF] Atag | Aviation benefits beyond borders. Air Transport Action Group[END_REF].

In Latin America region, two different situations can be pointed out in two largest markets: Brazil and Mexico. A deceleration process was particularly pronounced in Brazil meanwhile the Mexican economy strengthened as increased business and consumer confidence sustained domestic demand [START_REF] Airbus | Global Market Forecast 2015-2034[END_REF].

Traffic growth tendencies bring a lot of benefits but also disadvantages, perhaps one of the most prominent is related to system capacity. It has been predicted an expansion of passenger and cargo traffic and greater aviation connectivity, but with its corresponding increase in workload to airport services and air traffic control activities, among other elements of the system.

Helping to make best use of the available capacity at an airport combined with a more efficient, and predictable, arrival sequence can enhance the airport and air traffic management system capacity. Furthermore, this approach leads to a reduction in tactical intervention by the Air traffic controllers, but also leading to lower fuel consumption, less noise and pollution around the airport.

The present work aims to deal with capacity problem from the air side point of view by analyzing the Terminal Maneouver Area (TMA) route configuration. The proposed approach uses Genetic Algorithms to tackle the merging and sequencing problem to find a conflict free set of landing routes; and a discrete event simulation model to deal with the stochastic parameters of the system. The overall objective is to build a robust modeling technique which exploits the advantages of both optimization and simulation techniques to solve a complex problem as the merging and sequencing at TMA.

The reminder of this works is as follows; Section 2 provides an overview of the most prominent solutions to enhance capacity making emphasis in the airside solutions. In Section 3, it is presented the current and proposed route structure for Queretaro TMA. Following this, the proposed approach to solve the merging and sequencing problem is presented and explain in detail in Section 4. Section 5 contains some preliminary results. Finally, conclusions and future works are discussed at the end of the paper.

TRAFFIC GROWTH PROMINENT SOLUTIONS

To overcome the problems generated by the continuous growth of commercial aviation, a revisit or development of diverse philosophies is crucial. Airports, Air Navigation Service Provider (ANSP), and airlines among other stakeholders, share challenges and opportunities to develop or enhance their capacity. The most common ones include, in its pillars a collaborative decision making activity among all stake holders.

Approaches to alleviate air traffic congestion in dense regions (normally, metropolitan regions) include the development of an efficient Metropolitan Airport System (MAS). In the United States, the concept of an airport system was envisioned more than 50 years ago. According to [START_REF]Forecasting aviation activity by airport[END_REF], the basic guiding principles are: Airports should be safe, efficient, affordable to both users and government, they should be flexible and expandable to accommodate the increasing demand and be able to handle new aircraft and traffic types, they should be also compatible with the surrounding communities' needs, and they should contribute to the development of the region and national economy.

Airlines have implemented diverse approaches to meet traffic growth in an efficient manner and at a profitable cost. They have had to seek commercial partners to help them provide the network and service coverage required. Therefore, since 1990, alliances between airlines on international markets have become a dominant feature of the airline industry. One of the most important reasons is that alliances also allowed airlines to expand route systems with high quality standards without duplicating services that would add congestion.

Since the 70's, economists have tackle airport congestion by calling for the use of a price regulation mechanism. As a result, the airport peak load congestion pricing mechanism is proposed, which involves charging different landing fees at different times: during peak hours, flights are charged higher rates than during off-peak hours.

Regarding the airside, diverse modernization projects such as The Single European Sky ATM Research (SESAR) launched by the European Community and the Next Generation Air Transportation System (NextGen) launched by US government, among others, are aimed to ensure the safety and fluidity of Air Transport over the next thirty years. These projects are revisiting some key aspects to overhaul airspace systems. They are developing new philosophies and a variety of airspace concepts to satisfy strategic objectives such as increase safety, capacity and flight efficiency, i.e. reduce congestion, increasing operational efficiency in both air and land side, augment flight efficiency and mitigate environmental impact.

Airspace Concepts include details of the practical organization of the airspace and its operations as well as the CNS/ATM assumptions in which they are based. Practical organization of the airspace includes revisiting the ATS route structure, separation minima, route spacing, sector configuration and obstacle clearance. In the capacity and airspace utilization planning, the traffic flows demand plays an essential role in an efficient organization of airspace volumes which could increase the airspace capacity if properly addressed. At the same time, airspace control management must be undertaken to minimize the risk of potential conflicts while maximizing users' initial business interests' choices as often as possible [START_REF] Eurocontrol | Challenges of Growth 2013" Task 4: European Air Traffic in 2035[END_REF].

At major airports, airspace congestion has become a severe problem, especially at international hub or multiairport systems serving major cities and tourist destinations. The need for integrating related operations of areas with a high density of traffic like the TMA, is a primary concern to alleviate air traffic congestion while maintaining safe operations.

To optimize the structure of flows involved in localized congested areas, the change in their associated topology in terms of 4D Trajectories is proposed (trajectories defined in the three spatial dimensions together with a time-stamp) as one of the bases, including adherence to an agreed upon or constrained time of arrival and the improvement of spacing, sequencing and merging accuracy with the use of an adapted ground system automation support toolset.

Diverse approaches, both exact and heuristic, have been proposed to deal with the merging and sequencing problem in TMA but recently the approximate algorithms gained importance in the literature.

It was introduced a decision methodology called Constrained Position Shifting (CPS) [START_REF] Dear | The dynamic scheduling of aircraft in the near terminal area[END_REF] and [START_REF] Balakrishnan | Scheduling aircraft landings under constrained position shifting[END_REF] presented a CPS heuristic for the static and dynamic case of the Aircraft Landing Problem (ALP). The ALP aims at deciding a landing time for each aircraft such that each one lands within predetermined time window and that separation standards are respected. Different approaches for the ALP have been studied, some implement the CPS method and some others develop their own heuristics. For example, a Dynamic-Programming-based approach which used a method called Constrained Position Shifting (CPS) as in [START_REF] Balakrishnan | Scheduling aircraft landings under constrained position shifting[END_REF] and [START_REF] Balakrishnan | Algorithms for scheduling runway operations under constrained position shifting[END_REF], it is a class of algorithms that is able to handle commonly-encountered operational constraints for the sequence problem. In [START_REF] Beasley | Scheduling aircraft landings -the static case[END_REF] another approach which is based on Linear Programming solves the static case presenting a mixed-integer zero-one formulation of the problem together with a population heuristic algorithm. The CPS idea has been previously addressed by the authors in [START_REF] Zuniga | A cd&cr causal model based on path shortening/path stretching techniques[END_REF] using it to merge and sequence aircraft with a causal modeling approach.

In most European and North America TMAs, Arrival tools such as Arrival Manager (AMANs) systems or Final Approach Spacing Tool (FAST) have been developed to provide automated sequencing support for the ATC handling traffic arriving to an airport, continuously building arrival sequences and times for flights, taking into account the locally defined landing rate, the required spacing for flights arriving to the runway and other criteria. Unfortunately, when relying on open-loop vectoring techniques, the sequence manager is not fully aware of controllers' intentions and hence its purpose of building an efficient sequence is not achieved, besides, holding patterns may result when TMA capacity is exceeded at peak periods [START_REF] Eurocontrol | Challenges of Growth 2013" Task 4: European Air Traffic in 2035[END_REF].

Other proposals deal with the design of RNAV routes and terminal procedures, including departure procedures (DPs) and standard terminal arrivals (STARs). RNAV is a method of navigation that permits aircraft operation on any desired flight path within the coverage of ground or space based navigation aids or within the limits of the capability of self-contained aids, or a combination of these. Arrival RNAV & P-RNAV procedures have been defined in some TMAs with the aiming at airspace capacity, workload, efficiency, predictability and environmental benefits procedures.

Approaches such as the method called "Point Merge technique" presented by [START_REF] Boursier | Merging arrival flows without heading instructions[END_REF] and [START_REF] Favennec | Point merge integration of arrival flows enabling extensive RNAV application and CDA -operational services and environment definition[END_REF] aims to merge arrival flows of aircraft of traffic into a safe and efficient sequence without relying on open-loop vectors. Its objective is to achieve the aircraft sequence on a point with conventional direct-to instructions, using predefined legs at iso-distance to this point for path shortening or stretching. In [START_REF] Zúñiga | Causal model to sequence and merge 4DT flows in TMA[END_REF] a topology structure similar to the Point merge approach has been proposed to deal with the CD\&CR in both, En-Route and TMA using a causal approach. The main difference corresponds to the pre-defined topology used to expedite or delay aircraft and the use of path and speed regulation. In [START_REF] Zuniga | Integrating and sequencing flows in terminal maneuvering area by evolutionary algorithms[END_REF] an evolutionary algorithm has been developed to merge and sequence aircraft in TMA using two different topologies structures; it aims at optimizing the distance and therefore the delay introduced. Unfortunately, these procedures are not applied worldwide and when they are applied is mainly under low or medium traffic loads but not when high traffic loads are arising, and therefore, their major benefits have not been exploited.

CASE STUDY ROUTE STRUCTURE

In the last decade, the total passenger traffic has been growing at an average of 4.6% (RPK). According to [START_REF]Secretaria de Comunicaciones y Transportes "Aviación mexicana en cifras 1989-2012[END_REF], in 2014, the total number of operations reached more than 1 million from which 800 000 of the total correspond to domestic flights. Mexico transported over 65 million passengers through almost 750 regular routes, 53% of them were international and heading to United States. The domestic airline sector has been growing faster than the international one, it were transported 40.6 million passengers (62.5% of the total) while the international only increased a 7% moving 24.4 million passengers.

Mexico moved 617 500 tons of cargo in 2012, which represent a 5.6% increase in comparison with 2013. As for passengers, the international cargo volume grow at a faster rate than the domestic sector, it increased in 7.9% over the previous year transporting 56.9% of the total.

Mexico counts with 76 airports, 63 of them are international airports and 13 domestic, in addition there are 1431 aerodromes register in the country. This places Mexico as one of the countries in Latin America with the biggest airport network. The busiest airport in Mexico is called Mexico City International Airport (ICAO code: MMMX), which also conforms, since 2003 the pillar of the Metropolitan Airport System (MAS), together with 4 international airports: Toluca (ICAO CODE: MMTO); Queretaro (ICAO code: MMQT); Puebla (ICAO code: MMPB); Cuernavaca (ICAO code: MMCB) [START_REF]Estadística histórica[END_REF].

From the total passenger movements in 2014, the Metropolitan Airport System has moved around 31 million which represent 54% of the total passenger transported. The cargo sector moved around 70% of the volume.

As part of the MAS, and due to the nature of the industrial region in Queretaro, airport and government authorities have boost the airport cargo services. Queretaro International Airport contributes with around 4% of total cargo in the country. However, in recent years, Queretaro International Airport have observed an amazing growing rate of 17.5% and 1.7% in international and domestic cargo, respectively.

Furthermore, in the last years, Queretaro City and its suburbs have been developing a strong aeronautical industrial region as an initiative of Mexican Government. Nowadays, it can be found enterprises such as General Electric, Bombardier, Grupo Safran, ITR, Scema, among others. It also hosts one of the biggest heavy maintenance facility, (Maintenance, Repair and Overhaul, MRO), leaded by Grupo Aeroméxico and Delta Air Lines.

Queretaro International Airport has being hosting DHL hub operations since 2010. Its infrastructure was designed to process 40 tons daily. However, since September 2014, cargo operations are held in an area of 10 000 m 2 that has the capacity to move around 140 tons per day, which translates in an increment of 45%. Nowadays, DHL operates 12 daily flights in addition to 15 ground routes, connecting Queretaro to sites such as Ciudad Juarez, Chihuahua, Monterrey, Hermosillo, Ciudad Obregon, Mazatlan, Villahermosa, Culiacan, La Paz, Cabo San Lucas, Cancun, Merida and Mexico City, among others [START_REF]Estadística histórica[END_REF].

Due to the increasing demand within Queretaro International Airport, it is needed an efficient use of airspace, which includes predictable and efficient landing and departing operations. Therefore, a review of landing and departure operations, procedures and airspace configuration is needed to enhance airspace and airport capacity.

Landing route configuration

Fig. 1 shows Queretaro TMA chart, it can be found in it, information regarding minimum speeds and altitudes, airspace classification and main VORs and entry routes, among other important information. Fig. 2 depict the landing route structure for runway 27L/09R and 09L/27R, respectively.

In arrivals using runway 09L/27R, eight landing routes fuse into one single route towards the final approach (runway 09L/27R) by merging in one waypoint called D12.0 and following a final sequence denoted by D8.0, D6.0, D4.0 and D7.0 waypoint until threshold. In the arrival using runway 27L/09R six routes fuse into one single route towards the final approach (runway 09L/27R) by merging in one waypoint called D12.0 and following a final sequence denoted by D9.0, D6.0, D1.4 and D7.0 waypoint.

The proposed landing route configuration is designed using a radius of 50NM center at the airport to define TMA in accordance [START_REF]Estadística histórica[END_REF]. designing an alternative route configuration, it is needed to clarify some concepts such as alternative route and links. The alternative routes aim to deviate aircraft to solve potential conflicts detected between TMA entry points until final approach meanwhile an optimized sequence is built. An alternative route is conformed by diverse numbers of links which join an Entry point to runway. A link is defined as a portion of a route which connects two waypoints (or nodes). In previous works of the authors [START_REF] Zuniga | A cd&cr causal model based on path shortening/path stretching techniques[END_REF] and [START_REF] Zúñiga | Causal model to sequence and merge 4DT flows in TMA[END_REF], different route configuration and modeling approaches have been developed using Gran Canaria, Spain TMA. The different route configuration aims to avoid conflicts among aircraft by absorbing delays by a route change maneouver. Each alternative route conserves its Flight level constraints and lateral separation minima (based on ICAO document DOC-4444), as well as other airspace considerations such as avoid restricted, prohibited or any other areas not allowed for commercial flights.

Landing route configuration is designed to cope with the routes more congested. According to [START_REF]Estadística histórica[END_REF], the most congested routes are 2 international and 3 national: Fig. 3 (upper part) presents the proposed arrival route structure for runway 09L\/27R. There are eight entry points and one main merging point (20 18 20N 100 13 38W. All routes have been designed to maintain a minimum altitude, as dictated by Mexican government authority. As an example, see the bottom of Fig. 3 and which introduces route MALTA-N26-N22-N21-N17-N15-N14-RWY. This route has its maximum elevation of 2569 MSL at the first link (between MALTA and N26). All proposed routes were subjected to a review of its elevation constraints, some of them were discarded and some of them modified as needed.

Scenario

Table 1 shows Queretaro scenario used within the case study. The scenario investigated test 38 aircraft on 1 hour period. As input for the model, the entry point, aircraft type, entry time and speed are donated. For the optimization model, the average entry speed has been used meanwhile, for the simulation tests, a triangular distribution has been employed to introduce stochasticity within the aircraft speed.

The results have proved to find optimal solutions for both topology structures, the current one and the one proposed within section 3.1 and depicted in Fig. 3.

PROPOSED METODOLOGY

Optimization model

To test the benefits of the proposed landing structure, a genetic algorithm has been employed to schedule a set of landing aircraft. The objective of scheduling a set of landing aircraft is to determine the landing times and sequence of a set of landing aircraft in a particular runway so as to increase the runway throughput while satisfying diverse operational and safety constraints. mathematical formulation has been previously presented in [START_REF] Zuniga | Integrating and sequencing flows in terminal maneuvering area by evolutionary algorithms[END_REF] and it has proved to give good results in other scenarios.

The TMA has been modeled by a graph:

A N G ,  (1)
Where: N, represent the set of nodes and, A, represent the set of links.

For each route rj, it is defined a set of alternative routes, noted as alt(rj). These alternative routes are noted as:

   ) ( 1 j r L k k j r (2)
Where: L(rj) is the number of links of route rj, having alternatives choices. The mathematical formulation requires the following parameters:

Simulation model

The simulation model has been developed using a general purpose simulation software called SIMIO (SIMIOweb, 2015). Fig. 4 depicts the simulation introduced in section 3.1.

For the conflict detection it has been implemented the logic: a conflict is detected if a pair of aircraft flying in the same route have lost it separation minima (based on ICAO document DOC-4444). In case a conflict is detected, a delay is induced to the following aircraft by amending its speed and route. Fig. 5 top shows the coding wake vortex separation in SIMIO comparing the leading and the following aircraft separation.

Route selection depends on the delay required. As for the merging point technique [START_REF] Favennec | Point merge integration of arrival flows enabling extensive RNAV application and CDA -operational services and environment definition[END_REF], it is proposed an enveloped of predefined routes which are easy to select by controllers (see Fig. 6). Speed changes are employed to couple the speeds for leading and following aircraft to avoid catch up encounters. Fig. 5 bottom shows the coding for speed and route selection. All speed and route changes are performed when entering a link segment of the route. In addition, a reduction of 10% of its current speed is performed to slow down the aircraft for landing.

Results

The genetic algorithm parameters used for the genetic algorithm are presented in Table 2. The simulation report can be used to investigate the a wide variety of parameters such as time of an aircraft within the route, average, maximum and minim speed, number of conflicts encountered, number of speed and route changes, average number of aircraft in a link or route, among others. Fig. 9 introduces some of the possible results for the simulation model in a 100 run experiment when investigating each aircraft type statistics. Fig. 10 shows an example of link statistics, where the number of aircraft in the link together with is spent time in it can be noticed. Finally, Fig. 11 presents statistics about runway such as utilization and average processing time per aircraft, among others.

Conclusions

The present work introduces a new methodology that combines an optimization technique, such as genetic algorithms with discrete event simulation to perform the merging and sequencing problem at TMA. One, and perhaps the most valuable benefit of the proposed methodology relies on the ability to deal with both deterministic and stochastic characteristics of real problems resulting in a more robust and reliable solution.

Figure 1 Figure 2

 12 Figure 1 Queretaro air space configuration

  Queretaro-Houston, Queretaro-Monterrey, Queretaro-Dallas, Queretaro-Cancun and Queretaro-Mexico. Three routes (Houston, Monterrey & Dallas), normally enter by the norther waypoints: VITOS, PITIC, PENRA, or PLADE. The other two routes (Cancun & Mexico) enter by the south KOBEK, ROSMA or MALTA.

Figure 3

 3 Figure 3 Synthetic arrival routes, runway 09L/27R

  fi: the flight planned to land in a given time horizon [0,Tmax], fi = {1, … , n}, ei: the entry point of flight fi in the TMA i ϵ fi, ti: the time of flight fi at entry point i ϵ fi, yi: the speed of aircraft (fi) i ϵ fi, rj: the original route of aircraft (fi) i ϵ fi, wti: the wake turbulence category (heavy, medium, light) Entry point Aircraft type Entry time [h] Entry speed [km/h] mssik: the required minimum safe separation between aircraft i and k if i lands before k, mssij ≥ 0 i , k  fi due to their wake vortex constraint. d(fi, fj): the distance separating aircraft i and k if i lands before k. The modeling approach considers two kinds of conflicts: Node conflict and Link conflict. A Link conflict is predicted if aircraft flying on the same link have lost the minimum safe separation (mssik) between aircraft i and k depending on the aircraft's wake turbulence category, i.e. mssij ≥ d(fi , fj)  t [0,T] d(fi , fj) , if i lands before k, mssij ≥ d(fi , fj)  i , k  fi ). A Node conflict is predicted when an aircraft fi is flying over a node nk, other aircraft have to be 5NM away from the node. The optimization process is subject to speed constraint mssij  fi  F vi  [vimin , vimax]

Figure 4

 4 Figure 4 Simulation model

Figure 5 Figure 6

 56 Figure 5 Simulation model

Fig. 7

 7 Fig. 7 and 8 represent the evolution of the fitness features with generation for the 38 aircraft scenario. The evolution of the fitness features is summarized for which the fitness of the best individual, the average fitness on population and the standard deviation are plot with generations.

Figure 7 Figure 8 Figure 9 Figure 11

 78911 Figure 7 Evolution of the fitness for Queretaro, Mexico TMA

Table 1 .

 1 Margins and Column Width

Table 2 .

 2 GA parameters

		38 aircraft scenario
		parameters
	Number of generation	100
	Pop size	100
	Probability of Crossover	0,3
	Probability of Mutation	0,3

Vitos Light 0.014722222 Triangular(516.708,574.12,631.532) Masil Medium 0.050833333 Triangular(466.704,518.56,570.416) Plade Medium 0.1125 Triangular(516.708,574.12,631.532) Fresa Medium 0.278333333 Triangular(516.708,574.12,631.532) Pitic Light 0.328333333 Triangular(466.704,518.56,570.416) Vitos Light 0.417222222 Triangular(516.708,574.12,631.532) Masil Medium 0.470555556 Triangular(466.704,518.56,570.416) Penra Light 0.528888889 Triangular(516.708,574.12,631.532) Xosas Light 0.5975 Triangular(466.704,518.56,570.416) Fresa Heavy 0.668055556 Triangular(466.704,518.56,570.416) Penra Light 0.723333333 Triangular(516.708,574.12,631.532) Xosas Medium 0.783888889 Triangular(466.704,518.56,570.416) Vitos Light 0.861944444 Triangular(516.708,574.12,631.532) Masil Light 0.9175 Triangular(466.704,518.56,570.416) Masil Medium 0.073333333 Triangular(483.372,537.08,590.788) Plade Light 0.074166667 Triangular(483.372,537.08,590.788) Pitic Heavy 0.074444444 Triangular(483.372,537.08,590.788) Fresa Light 0.132777778 Triangular(516.708,574.12,631.532) Vitos Light 0.222777778 Triangular(483.372,537.08,590.788) Masil Heavy 0.276388889 Triangular(516.708,574.12,631.532) Plade Medium 0.3075 Triangular(483.372,537.08,590.788) Fresa Medium 0.358611111 Triangular(516.708,574.12,631.532) Malta Light 0.473055556 Triangular(516.708,574.12,631.532) Penra Medium 0.530277778 Triangular(483.372,537.08,590.788) Vitos Light 0.611666667 Triangular(516.708,574.12,631.532) Plade Heavy 0.672777778 Triangular(483.372,537.08,590.788) Fresa Medium 0.736666667 Triangular(483.372,537.08,590.788) Pitic Light 0.806111111 Triangular(516.708,574.12,631.532) Penra Light 0.919166667 Triangular(483.372,537.08,590.788) Vitos Light 1.001388889 Triangular(516.708,574.12,631.532) Masil Medium 0.073333333 Triangular(483.372,537.08,590.788) Malta Light 0.242222222 Triangular(483.372,537.08,590.788) Xosas Light 0.398333333 Triangular(483.372,537.08,590.788) Vitos Medium 0.501666667 Triangular(483.372,537.08,590.788) Pitic Heavy 0.573333333 Triangular(483.372,537.08,590.788) Fresa Light 0.796666667 Triangular(483.372,537.08,590.788) Malta Medium 0.960277778 Triangular(483.372,537.08,590.788) Xosas Light 1.042777778 Triangular(483.372,537.08,590.788)

ACKNOWLEDGMENTS

The authors acknowledge all the support provided by the National Council of Science and Technology of México (CONACYT).


T Chabardès

P Dokládal

M Faessel

M Bilodeau

A PARALLEL, O(N) ALGORITHM FOR UNBIASED, THIN WATERSHED

Keywords: Segmentation, Watershed, Local implementation, Linear time

The watershed transform is a powerful tool for morphological segmentation. Most common implementations of this method involve a strict hierarchy on gray tones in processing the pixels composing an image. Those dependencies complexify the efficient use of modern computational architectures. This paper aims at answering this problem by introducing a new way of simulating the waterflood that preserves the locality of data to be processed. We propose a region growth algorithm based on arrowing graphs that is strictly linear despite the valuation domain of input images. Simultaneous and disorderly growth is made possible by using a synchronization mechanism coded directly on the weight of nodes. Experimental results show that the algorithm is accurate and by far outperforms common watershed algorithms.

INTRODUCTION

The watershed transformation is a common tool for morphological segmentation. It is based on region growth and edge detection. One definition reflects the water flood on a topographic relief. This definition creates thin watershed lines and was chosen for the most used algorithms. Considering the topographic surface as pierced at the location of regional minima, it is immerged in water, so that the water rises from those holes and creates lakes. Those different lakes, each associated with a minimum, are not allowed to mix and their intersections will form dams. The set of all dams is called the watershed lines and represents the desired contours.

Algorithms that replicate this principle do not meet the speed required by the ever-growing amount of data to be processed. The queue-driven propagation is very sequential and only efficient for mono-processors. The current limitation of the clock rate limited by physical constraints brought the need for multi-processor architectures and adaptation of usual methods to the new specifications. The sequential nature of most algorithms makes impossible to benefit of their parallel processing capabilities. This motivates the work presented in this study.

In this article, we present a new method to calculate watershed lines using an oriented graph or digraph. Compared to traditional methods, the proposed method preserves the locality of data and allows for optimized implementation without compromising the quality of the extracted contours. Time complexity is still linear with respect to the number of pixels and the use of complex data structures such as hierarchical queues is avoided. We compare ourselves with the two following methods: a hierarchical queue-driven propagation [START_REF] Beucher | The morphological approach to segmentation : the watershed transformation[END_REF] and successive geodesic thickenings of the regional minima [START_REF] Meyer | Topographic distance and watershed lines[END_REF].

RELATED WORK

Early work involved morphological operators. Reconstruction of successive thresholds of the image, by means of skeleton by geodesic influence zones, has been developed in [START_REF] Beucher | Use of watersheds in contour detection[END_REF] by Beucher and Lantuejoul. Iterations are calculated until idempotence to obtain the watershed.

Another iterative approach based on arrowing has been introduced in 1990 by Beucher [START_REF] Beucher | Segmentation d'Images et Morphologie Mathématique[END_REF]. A more recent method using successive pruning of the arrowing graph has been developed by Meyer in 2014 [START_REF] Meyer | Construction du watershed par fléchage et elagage des chemins d'inondations[END_REF].

Other approaches involving the use of hierarchical queues were first introduced by Vincent and Soille in 1991 [START_REF] Vincent | Watersheds in digital spaces : An efficient algorithm based on immersion simulations[END_REF] and by Meyer [START_REF] Meyer | Un algorithme optimal de ligne de partage des eaux[END_REF][START_REF] Beucher | The morphological approach to segmentation : the watershed transformation[END_REF] and developped by Beucher in a non-biased algorithm [START_REF] Beucher | Algorithmes sans biais de ligne de partage des eaux[END_REF]. Splitting the image into smaller images was studied in 1996 [START_REF] Bieniek | A parallel watershed algorithm[END_REF] by Bieniek and al., with a preprocessing of the overlapping areas and distribution of those images to multiple processing units. A study was realized on the parallelization of the hierarchical queue approach by Beucher in 1997 [START_REF] Beucher | Réalisation de la ligne de partage des eaux par file d'attente hierarchique parallèle[END_REF]. Further works on splitting by Gillibert and Jeulin involved iterative processing of smaller images and a merging procedure of the results until idempotence [START_REF] Gillibert | Stochastic multiscale segmentation constrained by image content[END_REF].

An alternative definition of the watershed transform based on topologic distance was proposed in 1997 by Couprie et Bertrand [START_REF] Couprie | Topological grayscale watershed transformation[END_REF]. Futher works lead to the creation of the power watershed by Couprie, Grady, Najman and Talbot in [START_REF] Couprie | Power watershed: A unifying graph-based optimization framework[END_REF]. Parallelization of this method was studied in [START_REF] Van Neerbos | Mathematical morphology and its applications to image and signal processing[END_REF] by van Neerbos, Najman and Wilkinson. Addionally, a first massively parallel algorithm in pseudo O(n) in continuous space was proposed by Dejnozkova [START_REF] Dejnozkova | Architecture dédiée au traitement d'image base sur les équations aux dérivées partielles[END_REF][START_REF] Dejnozkova | A parallel algorithm for solving the eikonal equation[END_REF].

TOPOGRAPHIC STRUCTURES

We define a gray-level image by the mapping f : D → V , where D is the set of pixels and V the valuation domain. We associate this function with its corresponding topographic relief, where all gray values can be seen as elevations on the relief. This topographic relief contains a various number of topographic structures such as domes, valleys, ridges, thalwegs, regional minima, plateaus, and so on. Among those, a few interest us as flooding paths, plateaus, regional minima and catchment zones. The absolute heights of the pixels are not needed for defining the topographic structures and they depend only on the relative heights of neighboring pixels.

In the following, ∼ denotes the neighborhood relationship on D defined by the considered connectivity. Any usual connectivity can be used, e.q. 4,6 or 8 in 2D and 6,18 or 26 in 3D.

     f (a) < f (b) ⇔ a is a lower neighbor of b, noted a ≺ b f (a) > f (b) ⇔ a is a higher neighbor of b, noted a b f (a) = f (b) ⇔ a, b are level-neighbors, noted a b
We introduce a graph G (N, E), a non-oriented graph where N ↔ D and the set E is generated by the connexity ∼. We can encode the relative height of neighboring nodes in an oriented graph built from the previous graph, by defining edge sets derived from E. We note E ≺ , E and E the edge sets generated by the relation ≺, , . Using these new edge sets, we can define the increasing graph G (N, E ), the decreasing graph G (N, E ≺ ) and the level-neighbor graph G (N, E ). Considering a ≺ b ⇔ b a, The two following properties can be deduced: For a point a the transitive closure + of a defines a plateau p, a connected region of a constant-level, with a ∈ p. From now on, let P = i p i denote the set of all plateaus and p i its elements.

G (N, E ∪ E ≺ ) is non-oriented, G (N, E ) is non-oriented.
A plateau from where one cannot reach a lower altitude with a non-increasing path is called regional minimum. We can define it using the following equation:

m ∈ P, m is a regional minimum ⇔ ∀a ∈ m, b ∈ N, a ≺ b.
We call the set M = i m i the set of all minima.

Given some minimum m i , the transitive closure + defines the catchment basin of m i : CB(m i ) = {x | x + y, y ∈ m i } as the union of points connected to m i by a strictly decreasing path.

The basins are not disjoint. Their intersection is usually considered as the watershed. However, this intersection does not have the necessary properties, namely it is neither thin nor contiguous. We show below how to efficiently generate a thin, continuous and well centered watershed line, and define the subset later as an union of nodes and edges.

BUILDING THE WATERSHED USING THE FLOODING GRAPH

In the next section, we show how a flooding graph can be used to generate the watershed lines. We describe the three main components of the method in sections 4.1, 4.2 and 4.3.

Reconstructing the catchment basins requires the extraction of minima and the creation of the flooding graph. However, those two last components are independent. Figure 1 shows how they relate to each other. The result l(f ) holds both partial catchment basins and watershed lines.

M Label Reconstruction f l(f ) d pi∈P E E ∪ eq (2)
eq (1)

G f lood markers Fig. 1. Overview of the method.

Minimum detection

The set of regional minima U is obtained by removing from P all plateaus p i that are not minima by

U = P \ {p i | ∃b, b ≺ a, a ∈ p i }, with a, b ∈ N
Note that this operation is an opening by reconstruction of P with a marker set V = {a | ∃b, b ≺ a} which is the decreasing border (provided it exists) of any plateau which is consequently not a regional minimum. Given that P contains plateaus, U does not contain singlepixel minimum. The set of single-pixel minimum is denoted by S, and is efficiently detected using S = {a | b, a b or a b} The set of all minima of an image, denoted by M , is the union of both regional and singleton minima, i.e. M = U ∪S. Figure 2 shows an example of this process.

Generating the flooding graph

Water flooding is a bottom-up process. A natural choice to simulate this behavior would be to use the increasing graph there is e b,a ∈E . Note that this graph contains no arcs on plateaus to indicate how to flood plateaus. On plateaus, water flows from decreasing borders towards increasing borders. In the following we create E arcs on plateaus to simulate this behavior as well. Consider some plateau p and its decreasing border V , V ⊂ p. Let d p (a, V ), a ∈ p, denote a geodesic distance in p from a to V . We redefine the set of increasing edges in the following way. Let a, b

∈ N | a ∼ b: e b,a ∈ E if f (a) > f (b) or d p (a, V ) > d p (b, V ) when a, b ∈ p (1)
Figure 3 shows how an increasing graph of the initial image is completed with an increasing graph of the geodesic distance of the plateau.

Catchment basin reconstruction

Each basin is associated to a minimum, the minima are labeled. For every node, we associate a value in L = {∅, W }∪ N * , where ∅ is an undetermined value, associated to every non-minimum node at initialization, W is the watershed line value. Thus, we define the application l : D → L . As the water rises from bottom to top, a node takes its label from the nodes below it. If the same label appears on all lower neighbors, this label propagates. Otherwise, if different labels are available, the value W is assigned. W itself does not propagate.

We note Q(a) = {l(b) | b a} \ {W } the set of labels on lower neighbors of a, and we propose the following rule of propagation:

repeat if Q(a) = {l}, l = ∅, then l(p) ← l else if |Q(a) \ ∅| > 1 then l(p) ← W. until stability (2)
The resulting image contains both the catchment basins associated to the minima, and the watershed lines. Depending on the chosen flooding graph, the shape and location of watershed lines can vary.

Thin watershed lines

Equation ( 2) suffices to produce a watershed segmentation. However, thick watershed lines appear whenever every lower neighbor are labeled W, i.e. Q(a) = {} in (2). Figure 4 shows an example of such a situation. We introduce a method 0 0 1 to modify the graph after a pass of basin reconstruction so that the unexplored nodes are flooded. Such nodes n, with Q(n) = {} are called blocking nodes. We note B = {n | Q(n) = {}} the set of all blocking nodes. We define the influence zones of each blocking node as Z(n) = {a | a + n, l(a) = ∅}. We suppress the edges from lower neighbors to nodes of Z(n).

1 1 1 1 3 2 3
E 1 ← E \ {e b,a | a ∈ Z(n), b a} (3)
We define the lowest reachable neighbors of a influence zone:

V = arg inf a f (a), l(a) ∈ N, b ∈ Z(n), a ∼ b.
Then we replace the missing graph on every influence zones so that water flows from the lowest reachable nodes:

E 2 ← E 1 ∪ {e b,a | a ∈ Z(n), b ∈ V , a ∼ b}. (4)
We complete the flooding graph on each Z(n), n ∈ B, similarly as equation ( 1):

E 3 ← E 2 ∪ e b,a | d Z(n) (a, V ) > d Z(n) (b, V ), a ∼ b (5)
Basin reconstruction can now explore the remaining nodes using G (N, E 3 ). Figure 5 shows an example of such modifications of the flooding graph.

EVALUATION

The proposed method produces result equal to the unbiased watershed as described in [START_REF] Beucher | Algorithmes sans biais de ligne de partage des eaux[END_REF]. The watershed line is not necessarily contiguous in a discret grid, as no biased choice is done. However, it is contiguous if we consider watershed to be on edges and nodes, see Figure 5(c). Computations of minima, distances, and reconstructions can be realized using simple queues as a propagation mean. Parallelism can be achieved for reconstructing basins using an atomic synchronization on each node. Minimum detection can also be parallelized and it requires no synchronization in a shared memory context.

Time measurement

We ran experiments on an Intel(R) Xeon(R) CPU E5-2650 v2 based shared memory parallel computer with 8 cores, running at a 2.60Ghz clock frequency. We performed time measurements using synthetic images generated by a distance function on random seeds. We compared our method, the Beucher's hierarchical queue method [START_REF] Beucher | Algorithmes sans biais de ligne de partage des eaux[END_REF] and the geodesic thickening Meyer [START_REF] Meyer | Topographic distance and watershed lines[END_REF]. Figure 6 shows the obtained results. The proposed method is almost 10 times faster than [START_REF] Beucher | Algorithmes sans biais de ligne de partage des eaux[END_REF], and 100 times faster than [START_REF] Meyer | Topographic distance and watershed lines[END_REF]. The obtained speed-up is high due to the use of atomic synchronisation.

CONCLUSION

We propose a method to calculate the watershed lines in O(n) that requires no sorting of pixels with respect to their elevations. It produces identical results to the unbiased version of watershed using the hierarchical queue proposed by Beucher in [START_REF] Beucher | Algorithmes sans biais de ligne de partage des eaux[END_REF]. This method is faster than conventional methods. Removing the sequential nature of the transform allows us to reach higher performances by exploiting parallel computation such as MIMD and SIMD paradigms. This approach shows that transformations of morphological mathematics that were considered difficult to parallelize efficiently can be optimized for recent architectures using simple operators such as arrowing graphs and atomic propagation.

  If a,b are neighbors, we write a ∼ b. For a, b ∈ D | a ∼ b:

  The relations , and≺ are transitive. If a b c then f (a) = f (b), f (b) = f (c) and also f (a) = f (c)and a is path-connected to c by a level-constant path. Similarly, if a b c then also f (a) > f (c) and a is connected to c by a strictly decreasing path.

3 Fig. 2 .

 32 Fig. 2. Minima detection. E (double-sided arrows), E (single-sided arrows). P = {p 1 , p 2 , p 3 }. V = {c, f, g}, decreasing borders. U = P \ {p 1 , p 2 } = {a, b}. S = {h}. M (f ) = U ∪ S = {a, b, h}.

Fig. 3 .

 3 Fig. 3. Generating a flooding graph. (a) gray-level image. (b) geodesic distance on a plateau. (c) flooding graph, ascendancy graph (black), ascendancy graph on the geodesic distance (red).

Fig. 4 .

 4 Fig. 4. Occurence of blocking nodes. (a) gray level image. (b) flooding graph, see eq (1), labeled minima (red, green). (c) reconstruction of basins get stuck at this stage. edges unexplored (black). blocking nodes (thick)

Fig. 5 .

 5 Fig. 5. An example of a modified graph. (a) result of one pass of basins reconstruction. (b) modified flooding graph, edges to lowest reachable nodes. (c) final basin reconstruction with nodes at value W (gray). Note that obtained watershed is discontinuous, but continuous if edges are considered as watershed (thick edges).

Fig. 6 .

 6 Fig. 6. Performances of the proposed method. (a) Comparison to the state-of-the-art methods. (b) Multi-thread Analysis.


Sandra Teston-Bonnard

Isabel Colón De Carvajal

Vassiliki Markaki-Lothe

Études des interactions dans les lieux de vie d'un patient aphasique : auto-répétitions, répétitions collaboratives, et reformulations des aidants

Introduction

Dans le cadre du projet « Interactions entre Aphasiques et Aidants » (IAA), développé sur l'axe Interaction et Santé du laboratoire ICAR, nous avons constitué une série d'enregistrements vidéo d'interactions entre des patients aphasiques et leur entourage proche privé (conjoints, amis, enfants, etc.) ou professionnel (soignants, thérapeutes, auxiliaires de vie, etc.) , tous ayant un rôle d'aidant auprès des patients. L'ensemble des détails de l'interaction mis en lumière par les données audio-visuelles sont transcrits et permettent de rendre visible la production située, dans le temps et en contexte, des pratiques langagières des participants.

Après une première lecture des données, nous observons la production d'un très grand nombre de répétitions et de reformulations de la part des aidants : parfois celles-ci se substituent au tour du patient à un point de transition possible, ou bien elles sont des répétitions ou des reformulations de productions issues d'un tour précédent.

Les répétitions et les reformulations semblent alors caractéristiques de ce type d'interactions. Ces réalisations sont organisées selon différents formats (par exemple, des auto ou hétérorépétitions produites à l'identique, ou avec modifications -modalisations, expansionsde manière contingente ou différée ; ou encore des auto-reformulations paraphrastiques et synonymiques (Picoche 2007 : 296)et remplissent différentes fonctions comme des répétitions à emploi d'intensité, de renforcement (Hammer 2007 : 35), ou des répétitions et des reformulations permettant de délimiter une période thématique dans laquelle les participants co-construisent du sens. De plus, ces phénomènes langagiers, traditionnellement catégorisés en linguistique interactionnelle comme des pratiques de réparation, renvoient à un aspect fondamental de la gestion de l'intercompréhension en interaction (Mondada & Pekarek Doelher 2000).

Nous proposons ici de décrire les propriétés des différents usages des répétitions et des reformulations dans des contextes particuliers d'interactions entre patients aphasiques et aidants, et entre les aidants en train de s'occuper conjointement du patient aphasique. La particularité de notre étude est d'articuler des approches syntaxiques [START_REF] Claire | Approches de la langue parlée en français[END_REF][START_REF] Claire | La naissance des syntagmes dans les hésitations et répétitions du parler[END_REF][START_REF] Sandrine | Amorces de mots et répétitions dans les énoncés oraux[END_REF] Dans une première partie, nous présenterons brièvement le projet et le corpus analysé, puis nous proposerons une analyse linguistique de cas.

Brève présentation du projet IAA

Le projet de recherche Interactions entre Aphasiques et Aidants est financé pour un an par le Labex ASLAN1 . Nous travaillons en collaboration avec des orthophonistes de la région Rhône-Alpes, et nos objectifs scientifiques fixés se structurent autour de deux axes: 1) un travail de collecte de données empiriques d'interactions entre des personnes aphasiques et leur entourage comme un accès privilégié aux manières dont les professionnels de santé accomplissent la remédiation langagière ; 2) un travail de description détaillée des procédés avec lesquels les acteurs construisent et transmettent des savoirs et des compétences communicationnelles spécifiques aux interactions impliquant des patients présentant des dysfonctionnements langagiers. Une analyse des interactions avec des personnes aphasiques peut ainsi contribuer à donner une plus grande visibilité à ces compétences, parfois encore marquées par un manque de reconnaissance académique au sein des organisations du travail et considérées comme des pratiques particulièrement hétérogènes [START_REF] Stanislas | L'ambivalence de la psychologisation des rapports de travail dans les institutions 'psy[END_REF].

A ce jour, nous avons enregistré deux patients aphasiques en conversation avec trois types d'interlocuteurs non aphasiques : sa conjointe, son orthophoniste puis une tierce personne. Les échanges d'un même patient sont donc documentés dans trois situations d'interaction, qui nous permettent de comparer les stratégies communicationnelles compensatoires développées par les locuteurs pour accompagner, aider et soutenir le patient dans l'élaboration d'un échange. Ainsi, nous avons deux patients, Daniel et Antoine, enregistrés lors d'un repas et d'une séance d'orthophonie. Pour Antoine uniquement, nous avons aussi des enregistrements lors d'une séance de kinésithérapie et d'activités avec une auxiliaire de vie (Colón de Carvajal, Markaki-Lothe & Teston-Bonnard, à paraître).

Répétitions et reformulations des aidants

Une approche syntaxique

Le contexte de la remédiation langagière relève du domaine de la (re)acquisition et du (re)apprentissage des pratiques discursives. Les échanges entre patients et aidants s'orientent vers ce (re)apprentissage où la reformulation semble jouer un rôle particulier. En effet, dans nos corpus nous identifions des séries de reformulations avec le sens de « re-dire le message d'une autre manière », dire qui peut comporter des explications, des illustrations, des exemples, comporter des répétitions ou même des reprises à l'identique. La définition des caractéristiques linguistiques des notions de la reformulation et de la répétition devient alors pertinente pour nos analyses.

Dans le domaine de l'acquisition et de l'apprentissage la reformulation aurait plusieurs fonctions2 :

une fonction de clarification lorsque le locuteur reformule son propre énoncé [START_REF] Aliyah | Processus de clarification de la référence dans le dialogue adulte-enfant[END_REF], ou lorsque l'interlocuteur cherche une confirmation de l'interprétation qu'il a donnée à l'énoncé de l'autre [START_REF] Eve | Énoncés enfantins et reformulations adultes dans l'acquisition du langage[END_REF], une fonction de réorientation du dialogue (reformulation « diaphonique », [START_REF] Weck | Reformulations et répétitions par les adultes du langage des enfants: comparaison de dialogues avec des enfants normaux et dysphasiques[END_REF],

une fonction phatique pour montrer à l'apprenant qu'on accueille ses productions, qu'on les prend en compte et qu'on essaye de les comprendre (Vinter 2000), une fonction « corrective » [START_REF] Eve | Énoncés enfantins et reformulations adultes dans l'acquisition du langage[END_REF]) ou « d'apprentissage » (Vinter 2000).

Le fait que les apprenants tiennent compte des reformulations et corrigent leurs productions erronées illustre, selon [START_REF] Eve | Énoncés enfantins et reformulations adultes dans l'acquisition du langage[END_REF], que « les reformulations servent l'acquisition ».

Les répétitions garantissent quant à elles « à la fois la progression, la cohésion et l'interprétabilité du texte parlé » (Krötsch 2007 : 37). Krötsch déclare que « la répétition est le support par excellence de l'activité langagière à l'oral » et poursuit en affirmant que « en faire une erreur de planification est aberrant : elle rend au contraire la planification à court terme possible dans la production et est en cela bien adaptée à la relance du texte parlé, foncièrement ouvert. » Henry (2002 : 2), après avoir bien établi la distinction entre la répétition « fait de langue » qui sont « des reprises d'éléments prévues par la grammaire, en opposition à (…) des répétitions « faits de parole », c'est-à-dire des répétitions propres à l'oral, véritables révélateurs de l'élaboration de tout discours oral », elle distingue aussi les répétitions de performance (en opposition aux répétitions de compétence), telles que nous nous sujet + complément, nous nous présentons, ou pronom disloqué : nous, nous viendrons. Les résultats montrent que les répétitions de performance concernent principalement les mots-outils et apparaissent à des frontières syntaxiques majeures (Henry 2005).

Si l'on observe plusieurs types de répétitions, on peut aussi se poser la question de l'existence de la répétition à l'identique. Selon Prak-Derrington (2008 : 251), le seul fait de répéter implique un changement de perspective énonciative ; par ailleurs, la notion d'identique est remise en question par le fait que le terme répété change de fonction [START_REF] Claire | La naissance des syntagmes dans les hésitations et répétitions du parler[END_REF]Krotz 2007 : 43).

Il s'agit maintenant d'observer ce phénomène dans les échanges avec des patients présentant des troubles du langage dus à une aphasie. Aura-t-on les mêmes fréquences, les mêmes distributions syntaxiques ? Qu'apporte ce phénomène à cette interaction particulière ?

Analyse de cas selon une perspective syntaxique et interactionnelle à partir d'un énoncé source produit par le patient aphasique

Dans ce premier extrait (ci-dessous), le patient (Antoine) initie un thème sur l'activité de « tondre le jardin » qui est repris ensuite par les aidants et l'on peut observer ici l'effet d'échos successifs que produisent les hétéro/auto répétitions/reformulations.

A la ligne 1, Antoine recherche le mot cible du thème initié à prononcer avec quelques hésitations et réussie à le dénommer par un verbe isolé en fin de tour. Après une longue pause de 1.1 secondes, qui n'est pas saisie par les interlocuteurs pour prendre leur tour, Antoine formule un énoncé déclaratif complet (ligne 4). Le kiné (ligne 5), en s'adressant à Antoine, montre la bonne réception de son énoncé comme une demande, une plainte qui ne peut être satisfaite à cette période de l'année.

Extrait 1 : Tondre le jardin Ensuite, après une pause de 1.5 secondes, Lisa répète partiellement le début de tour d'Antoine et hétéro-initie une séquence de réparation adressée à son mari et au kiné (« ça fait un an QUOI/ » (ligne 8). L'hétéro-réparation est complétée par le kiné au tour suivant qui reformule, le tour initialement produit par Antoine (l.9). A la ligne 11, Lisa répète le tour du kiné. Elle reprend alors l'argument donné par le kiné en ligne 6 en le reformulant (« c'est plus l` moment de tondre maint`nant\ »). A la ligne 18, le kiné reformule une dernière fois son propre énoncé (ligne 6) ainsi que celui de Lisa (ligne 11) en apportant un changement du sujet et du complément circonstanciel de temps (« on va pas tondre aujourd'hui/ ». L'analyse de cet extrait montre que les participants mobilisent pas ou peu des adresses directes vers Antoine.

Les fonctions communicatives de la répétition et de la reformulation à partir d'énoncés sources produits par les aidants

A l'écoute des données constituées pour cette contribution, plusieurs questions émergent :

-A quoi sont utiles sur un plan thérapeutique et/ou communicationnel les auto/hétéro répétitions et reformulations des accompagnants, alors que ceux-ci ne s'adressent que très peu au patient, et conversent entre eux, la plupart du temps, sans s'adresser à lui, sans même lui répondre directement quand celui-ci tente de répondre ou d'intervenir ? -Est-ce la présence (et l'attention supposée) du patient qui incitent les accompagnants à parler ainsi ? -Serait-ce la façon habituelle de parler de ces aidants ?

Il est bien entendu difficile voire impossible de répondre vraiment à ces questions sans devoir interpréter les données, ce qui n'est pas conforme à notre perspective de recherche.

Si la conservation des règles pragmatiques universelles chez ces patients a permis à Holland (1976) de constater que « les personnes aphasiques communiquent mieux qu'elles ne parlent » ; cependant, l'observation et l'analyse des répétitions dans différentes études ont conduit les auteurs à montrer que la répétition a plusieurs fonctions communicatives. [START_REF] Michael | Children's Conversation[END_REF] identifie deux fonctions majeures de la répétition dans le discours : exprimer l'accord ou l'intérêt, et maintenir le dialogue. Il remarque aussi qu'elle peut servir aussi bien dans l'acquisition des connaissances que dans l'acquisition des mots, tous deux ratifiés par la répétition (voir aussi Clark 2006).

Maintien de l'échange

Dans le dialogue, la répétition sert à maintenir l'échange, exprimer l'accord, l'intérêt [START_REF] Michael | Children's Conversation[END_REF]. Chaque fois que l'interlocuteur suivant répète un élément nouveau emprunté à l'interlocuteur qui précède, il augmente la base commune qu'ils partagent tous deux [START_REF] Eve | La répétition et l'acquisition du langage[END_REF]. En maintenant le dialogue, la répétition accomplit quatre fonctions :

elle signale l'attention qu'on prête à ce que dit l'autre ; elle constate l'usage de l'interlocuteur à cette occasion, et l'interlocuteur signale qu'il adopte les conventions du locuteur (ou qu'il les refuse) 3 ; elle ratifie ce que le locuteur a dit ; si la répétition ratifie, la répétition cible aussi.

Ainsi l'étude de la syntaxe dans l'interaction permet d'observer ce qui est répété, quels mots, quels groupes de mots, aussi bien au niveau des catégories grammaticales que des fonctions grammaticales, quels sont les termes et constructions répétés les plus récurrents. Il est alors possible d'évaluer ce qu'on cible le plus souvent, ce qui est « choisi » par l'interlocuteur.

Augmentation de la base commune

Pour cet extrait 2 (ci-dessous), il est aisé d'observer « l'augmentation de la base commune » : on peut examiner quelles informations, quels messages ont été répétés, recueillis, donc choisis par les interlocuteurs. Avec l'interaction maintenue par la répétition, une synthèse des informations importantes peut être faite.

On relève des auto-répétitions à l'identique de constructions verbales produites par le kiné : « c'est à la demande » (répété 3 fois, lignes 5, 8 et 15) malgré les validations de Lisa par le marqueur « voilà » (lignes 7, 9, 13 et 14) pour chacune des répétitions du kiné. On note également des hétéro-répétitions du kiné pour répondre à l'inquiétude de Lisa (énoncé source de Lisa « ils me disaient de::\ faire attention d` pas démonter », lignes 17-18, répété par le kiné « ça risque pas d` se démonter ; ça risque de faire mal », lignes 20-21).

3 C'est pourquoi l'observation de ce qui est répété, et de ce qui ne l'est pas est important pour l'analyse.

Extrait 2 : L'attelle au bras4 Il s'en suit une séquence d'échanges co-construite entre les aidants (ci-dessous), autour du thème du bras et de l'écharpe, où le kiné et Lisa produisent des énoncés répétés collaboratifs à partir du groupe nominal « la nuit » (lignes 23, 25 et 28), ainsi qu'à partir de constructions verbales « ça fait très mal ; i` doit s` faire mal ; coincé l` bras derrière » (lignes 26, 28, 34 et 35).

On observe ensuite une autre période thématique autour du sujet : « c'est Antoine qui doit décider de mettre l'écharpe censée soutenir son épaule ». Dans cette séquence, on relève des auto-répétitions de Lisa, comme la construction verbale « i` m'a dit » (lignes 47-48), marquant un discours rapporté qui lui permet de cautionner ce qu'elle dit de son conjoint. Ici, quand Lisa explique qu'Antoine refuse de mettre l'écharpe quand l'infirmier vient, elle parle d'Antoine à la troisième personne, comme s'il n'était pas présent. Antoine intervient pourtant : « mais je mets » (ligne 87) et Lisa reformule/répète ce qu'a exprimé Antoine : « et il le remet » ; « il le met » (lignes 89, 90), toujours à la troisième personne, sans s'adresser directement à lui. Après les reprises du segment à présentatif « c'est lui » (ligne 91), le kiné produit quatre auto-répétitions à l'identique de la construction verbale clivée « c'est lui qui gère » (lignes 92, 95 et 97-98) toujours sur le même thème. Les auto-répétitions du kiné sont « interrompues » par Lisa qui les valide avec la reformulation modalisante : « il gère bien hein » (ligne 96).

Ces affirmations injonctives paraissent paradoxales au regard de l'absence d'adresses directes de la part des accompagnants au locuteur aphasique. Tout se passe comme si on voulait qu'il reprenne les rênes sur certains aspects de sa vie, alors que dans le cadre de la communication langagière, il ne pourrait plus être maître ni même acteur. Les aidants valident par là-même une dissociation des domaines (communication langagière et certaines décisions concernant son état), dissociation qui pourrait être rediscutée lors des séances de débriefing avec la thérapeute, si elle est jugée problématique avec les progrès du patient.

Conclusion

Les phénomènes de répétition et de reformulation mettent en oeuvre des stratégies communicatives et discursives. Par cette étude, l'approche macro-syntaxique articulée à la perspective interactionnelle permet de poser que l'interaction maintenue par des répétitions et des reformulations fournirait des résultats différents par rapport à une interaction maintenue par d'autres stratégies langagières, puisque les interactants ont pointé certaines informations et pas d'autres. Les répétitions et les reformulations ont permis aux locuteurs comme aux interlocuteurs de souligner, focaliser et conserver des informations, différemment que s'ils utilisaient d'autres types de stratégies langagières.

Les stratégies interactionnelles observées dans cette étude de cas sont à mettre en relation avec les expansions interactionnelles telles qu'elles sont présentées par [START_REF] Mondada | L'exploitation située de ressources langagières et multimodales dans la conception collective d'une exposition[END_REF][START_REF] Mondada | L'analyse de « collections » de phénomènes multimodaux en linguistique interactionnelle : À propos de l'organisation systématique des ressources gestuelles en début de tour[END_REF]. Il s'agirait de procédés complémentaires, et ici, les expansions ajoutent des informations pour convaincre et avancer dans l'interaction du côté du locuteur. L'hétérorépétition cible les informations importantes, ou à retenir, du côté de l'interlocuteur.

Sur un plan syntaxique plus restrictif, on peut faire le lien entre ces phénomènes et les parallélismes syntaxiques qu'on trouve très régulièrement à l'oral, mais aussi avec les énoncés collaboratifs. D'une certaine manière les répétitions « continuent » le discours de l'autre et l'interlocuteur s'approprie alors une partie de ce discours qu'il a sélectionnée. En effet, les segments répétés sont souvent des noyaux syntaxiques (unité suffisante communicativement, correspondant à un acte de langage, Blanche-Benveniste 19905 ), unité autonome à valeur illocutoire, même s'il s'agit d'unités qui ne sont pas des noyaux macro-syntaxiques dans d'autres contextes, dont évidemment des unités non canoniques ou des constituants dépendants micro syntaxiquement qui ne sont pas habituellement des noyaux.

En tant que noyaux macro-syntaxiques, les segments répétés constituent des informations supplémentaires, des messages à eux tout seul ; la répétition/reformulation recatégorise des segments syntaxiques habituellement non autonomes sur le plan syntaxique comme sur le plan discursif. N'importe quelle catégorie ou constituant, quelles que soient leurs fonctions, sont alors interprétés comme noyaux.

A l'issue de cette étude, nous pouvons proposer des pistes de travail pour explorer ces premiers résultats, en termes de syntaxe et de linguistique interactionnelle. A partir d'autres enregistrements de patients différents avec d'autres aidants, il sera possible de vérifier si, comme on l'a vu dans cette contribution, les répétitions/reformulations :

permettent de donner un statut syntaxique et séquentiel particulier aux segments répétés par rapport à ce qui précède et ce qui suit, en facilitant les réajustements et les réparations, en orientant l'interaction différemment ; font progresser l'interaction et développent, puis clôturent la période thématique ; manifestent l'orientation des aidants vers des fonctions particulières de ces pratiques comme celle de l'apprentissage et de la (re

)

  et interactionnelles pour l'analyse d'un même corpus. Elle contribue aussi aux travaux qui s'intéressent au langage et aux processus cérébraux (Nespoulos 2006, 2010) tout en tenant compte des contingences contextuelles (Wilkinson, Beeke & Maxim 2010), et en observant les mécanismes des répétitions et reformulations, au niveau de régularités distributionnelles et de contraintes syntagmatiques (Blanche-Benveniste 2003) de certaines configurations syntaxiques mises en oeuvre.

  socialisation des patients ; peuvent servir à o ajuster le sens des actions et des émotions au plus près de la réalité du patient ; o rassurer l'entourage familial, le conseiller, l'informer ; o redonner le statut d'un membre à part entière au patientqui doit pouvoir décider et même initierparfois difficile à (ré) obtenir. En effet, dans le contexte particulier des échanges avec des patients aphasiques, nos premiers résultats montrent que les répétitions et les reformulations des aidants s'orientent vers l'établissement d'une compréhension mutuelle, mais qu'il est aussi possible d'explorer les limites des répertoires langagiers des patients (dimension évaluative). Parallèlement, la rééducation langagière (dimension rééducative), et plus largement une « reconstruction discursive » du monde (Guilhaumou 2005), seraient mises en jeu.

Le labex ASLAN : Advanced Studies on LANguage complexity, est coordonné par F. Pellegrino (laboratoire DDL), assisté par les coordinateurs adjoints S. Teston-Bonnard & G. P. Niccolai (laboratoire ICAR).

Il n'y a pas de travaux à notre connaissance qui traitent des conditions linguistiques de la reformulation dans la remédiation langagière; c'est la raison pour laquelle nous nous référons essentiellement aux travaux portant sur les interactions enfantsadultes.

Pour des questions de place, nous présentons des morceaux de l'extrait 2 car il serait trop long à intégrer dans son intégralité. Les séquences coupées sont notées par ((---)), cependant la numérotation reste continue pour faciliter l'analyse.

Le noyau qui est la principale unité macro-syntaxique, est défini ainsi par les auteurs fondateurs du concept : « on convient d'appeler « noyau » l'unité minimale de macro-syntaxe, qui permet de former un énoncé autonome. » (Blanche-Benveniste 1990 : 114). Et plus loin, l'auteure propose le critère suivant : « le noyau fondamental de l'énoncé coïnciderait donc avec un acte de langage. »

Remerciements


Ma Jun

Ma Shaoan

Ludovic Hofer

Thibaud Lambert Directed

Olivier Baudon

Julien Bensmail

Study of the article: "An O(k 2 n 2 ) Algorithm to Find a k-partition in a k-connected Graph"

Introduction

The goal of the project was to study in depth the article [START_REF] Ma | An o(k 2 n 2 ) algorithm to find a k-partition in a k-connected graph[END_REF], which, although pretends to answer positively to a difficult problem, surprisingly did not attract a lot of attention in the litterature. More precisely, in [START_REF] Ma | An o(k 2 n 2 ) algorithm to find a k-partition in a k-connected graph[END_REF] is proposed a polynomial-time algorithm for constructing a special kind of vertex-partition of any k-connected graph which necessarily exists according to [START_REF] Győri | On division of graphs to connected subgraphs[END_REF][START_REF] Lovász | A homology theory for spanning trees of a graph[END_REF]. According to a private communication from E. Győri mentioned in [START_REF] Shin Ichi Nakano | A linear-time algorithm for four-partitioning four-connected planar graphs[END_REF], the algorithm from [START_REF] Ma | An o(k 2 n 2 ) algorithm to find a k-partition in a k-connected graph[END_REF] should not be correct. Our goal was hence to verify if the algorithm was correct and if he had the claimed complexity. In order to have an entire comprehension of this article, we had have to search, read and understand several related articles.

Our very first task was to understand the algorithm. For this purpose, we have had to implement it in Java, using a framework which contains the implementation of several classic graph algorithms. We also have had to implement a k-connected graph generator in order to test both the validity and the complexity of the proposed algorithm. This allowed us to test our implementation.

Our implementation has pointed out the fact that specific executions of the algorithm lead to an endless loop. With those counter-examples, we prove that the algorithm proposed in [START_REF] Ma | An o(k 2 n 2 ) algorithm to find a k-partition in a k-connected graph[END_REF] has not the expected complexity and also is not correct. We propose slight modifications to this algorithm, ensuring that instead of falling in an endless loop, the algorithm will end with a fail state. This change makes this algorithm easier to use as a base for a new Las-Vegas algorithm.

Definitions

In this section, definitions about graph theory are presented. Most of the following definitions are taken from or inspired by Wikipedia, Wikibook and Diestel's Graph Theory book [START_REF] Diestel | Graph Theory : 3rd Edition[END_REF].

Types of graphs

Undirected simple graph: An undirected simple graph G is a mathematical object composed of a set V of vertices and a set E of edges and is noted G = (V, E).

An edge is an unordered pair {u, v} of vertices and is sometimes also denoted uv for short.

A graph is used to model relation between objects. The vertices represent the objects and the edges represent the relations.

Thereafter if it is not stated otherwise, by "a graph", we implicitely refer to an undirected simple graphs. Vertex degree: The degree of a vertex v in a graph is equal to the number of vertices adjacent to it and is noted d(v).

Acyclic graph:

A graph G = (V, E) is acyclic if for every pair {u, v} of vertices in V , there is no more than one path1 from u to v.

Directed graph: A directed graph is a graph whose edges are defined as ordered pairs (u, v). The edges of a directed graph are called arcs. u is called the head of the arc and v is the tail of the arc.

Subgraph: Given a graph G = (V, E) and a graph G = (V , E ), then G is a subgraph of G if and only if V ⊆ V and E ⊆ E .
Induced subgraph: Given a graph G = (V, E) and a set of vertices V ⊆ V , the subgraph G of G induced by V is the subgraph of G whose vertex set is V and whose edges are those of G whose two ends belong to Descendant: Let r be the root of a tree. Given two vertices v and w, if v lies on the unique path between w and r, then w is a descendant of v.

V , it is denoted G[V ].
Spanning tree: A tree T is a spanning tree of a graph G if it includes every vertex of G and is a subgraph of G.

Paths

Path: A path is a non-empty graph P = (V, E) of the form

V = {x 0 , x 1 , . . . , x k } E = {x 0 x 1 , x 1 x 2 , . . . , x k-1 x k }
where the x i are all distinct. The vertices x 0 and x k are linked by P and are called its ends; the vertices x 1 , . . . , x k-1 are the inner vertices of P . The number of edges of path a is its length, and the path of length k is denoted by P k . Note that k is allowed to be zero; thus, P 0 = K 1 .

Figure 6: A graph and one of its paths of length 4 (in green)

A B C D E F
Vertex-disjoint path: Two paths P and Q are disjoint if and only if they (possibly) share their ends but have no common inner vertices.

Cuts

Let G = (V, E) be a graph.

Cut: A cut C = (S, T ) is a partition of V into two subsets S and T .

Cut-set: The cut-set of a cut C = (S, T ) is the set of edge defined as {uv ∈ E|u ∈ S ∧v ∈ T }. Cut size: The size of a cut is the number of edges in the cut-set.

Articulation set: An articulation set C of a graph G = (V, E) is a subset of V such that the subgraph of G induced by V \ C is disconnected.

Connectivity

Connectedness: A graph G is connected if for every pair {u, v} of vertices, there is a path from u to v. Otherwise, the graph is disconnected.

k-connectedness: A graph is k-connected if deleting any set of fewer than k vertices does not disconnect the graph. Menger's Theorem: The Menger's Theorem is an important theorem concerning connectivity. It states the following fact: Let G be a undirected graph and u and v two distinct vertices. Then the size of the minimum vertex-cut for u and v is equal to the maximum number of vertex-disjoint paths from u to v.

Flows

Flow network: A flow network is a directed graph G = (V, E) whose edges have a nonnegative capacity, i.e. ∀(u, v) ∈ E(G), c(u, v) ≥ 0.

Flow: Let G be an oriented graph, which has two specific vertices: a source s and a sink t. A flow is a function which associates to each edge (u, v) ∈ E a real: f : V × V → R so that the following properties are met: • Capacity constraints:

∀(u, v) ∈ E, f (u, v) ≤ c(u, v) • Symetry: ∀(u, v) ∈ E, f (u, v) = -f (v, u) • Flow conservation: ∀u ∈ V -{s, t}, v∈V f (u, v) = 0
Maximum-flow Minimum-cut Theorem: The max-flow min-cut theorem [START_REF] Fulkerson | Computation of maximal flows in networks[END_REF] states that in a flow network, the maximum amount of flow passing from the source node to the sink node is equal to the capacity of the cut which has the minimum capacity. Győri-Lovász Theorem [START_REF] Győri | On division of graphs to connected subgraphs[END_REF][START_REF] Lovász | A homology theory for spanning trees of a graph[END_REF] states that k-connected graphs are k-partitionable for all k ≥ 1. However the two proofs of this theorem are not constructive. We are interested in polynomial algorithms which are capable of finding k-partitions in k-connected graphs.

Partitions

k-partition: Let G = (V, E) be a graph. {V 1 , ..., V k } is a k-partition of G, if and only if: • ∀i, G[V i ] is connected • k i=0 |V i | = |V | • ∀i, j ∈ {1, . . . , k} 2 , i = j, V i ∩ V j = ∅

Problem description

The algorithm proposed in the article [START_REF] Ma | An o(k 2 n 2 ) algorithm to find a k-partition in a k-connected graph[END_REF] claims to be able to find a k-partition in a k-connected graph in a polynomial time, and this no matter what is k. The complexity of the claimed algorithm for a graph

G = (V, E) with |V | = n is O(k 2 n 2 ).
The k-partition problem which the article pretends to resolve can be formally defined as follows. Given a k-connected graph G = (V, E), a set of k vertices R = {r 1 , r 2 , . . . , r k } and k integers S = {s 1 , s 2 , . . . , s i } summing up to the order of G. Find a partition P = {p 1 , p 2 , . . . , p k } of V such that for any i from 1 to k, p i contains r i and |p i | = s i . An illustrated example is presented in Figure 11.

k = 3 R = {a, g, c} S = {2, 1, 4} P = {a, f }, {g}, {b, c, d, e}

Algorithm description

Principles

The main idea of the algorithm proposed in [START_REF] Ma | An o(k 2 n 2 ) algorithm to find a k-partition in a k-connected graph[END_REF] is to expand different trees from the roots given as input. The specificities of this expansion is that it is both progressive and balanced.

It is progressive because the algorithm iterates over the different components. Each component will try to acquire free vertices (vertices which do not belong to a component) and if there is no free vertices among its neighborhood, it will try to steal a vertex from another component.

The algorithm is balanced because a component can only steal a vertex from a component which has a lower ratio of the number of wished vertices over the number of vertices currently owned by the component.

In order to avoid endless loops engendered by two components stealing the same vertex one after the other, a memory of the components to which a vertex has belonged is maintained.

A proof of the complexity of this algorithm is given in the article [START_REF] Ma | An o(k 2 n 2 ) algorithm to find a k-partition in a k-connected graph[END_REF]. This proof can be summarized as follows.

1. The number of iterations of the expansion is O(kn).

Every step of an iteration is O(m).

3. An existing algorithm with complexity O(m) allows to reduce the number of edges in a k-connected graph to a number of edge O(kn) [START_REF] Nagamochi | A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph[END_REF].

From those three properties, the authors affirm that the complexity of the algorithm is O(k 2 n 2 ). But, even if the second possibility can be verified and if the validity of the third one does nott influence the fact that this algorithm is polynomial, the proof of the first property seems to be wrong since we exhibit a counter-example in section 4.3.2, showing that the algorithm may loop endlessly.

Used data

As it was mentioned previously, the algorithm of [START_REF] Ma | An o(k 2 n 2 ) algorithm to find a k-partition in a k-connected graph[END_REF] partition the graph into trees. Thoses trees needs to be stored, so both vertices and edges of each tree must be memorized and updated through the execution. The tree rooted at v = r i is denoted T v .

The history of the trees to which a vertex has belonged is stored in a set of vertices. An HashMap with vertices as keys and a set of vertices as values can then be used to obtain the history of any vertex. The data are stored in a structure called treeNode and the set of roots whose tree has owned the vertex v is denoted treeNode [v]. It is important to note that the history of some vertices can be reseted in some specific cases (see section 3.2.4).

The feature ensuring that the expansion is balanced is called the p-value. Each tree has its own p-value which is defined as the number of vertices wished for the tree divided by the number of vertices currently in the tree. A tree which has a p-value of 1 is a component which has the right amount of vertices. When iterating over such a tree, nothing will be done, because it does not need to acquire more vertices.

Acquiring vertices

When iterating over a tree which needs to gain vertices, the first step is to compute the neighborhood of the tree, i.e. the vertices of the graph which are neighbors to one (or more) of the vertices of the tree but are not in it. If among this neighborhood, there is at least one free vertex, i.e. a vertex which does not belong to any tree. The tree will acquire all the free vertices of this neighborhood, except if there are more free vertices than required. In that case, the tree acquires enough vertices so that its order reached the desired size, but no more. The vertices to acquire are chosen randomly among the available ones.

Stealing vertices

If there is not any free vertex in the neighborhood of the tree, then it tries to steal a vertex from another tree. Several rules defines whether a vertex can be stolen or not.

• The root of a tree (i.e. the r i 's) cannot be stolen.

• A tree T v cannot steal a vertex u if T v belongs to treeNode[u].
• A tree cannot steal a vertex from another tree which has a lower p-value.

Once those three rules have been applied to remove some vertices of the neighborhood, if there is no vertex left, then the tree doest not steal any other vertex during this iteration. On the other side, if there are still multiple vertices remaining, then one vertex is chosen as the vertex to steal. The following procedure is applied.

1. Keep only the vertices which have the smallest p-value of the set.

2. Among this new set, keep only the vertices which have the smallest degree inside the tree.

3. If there are still multiple vertices, pick one randomly.

If the vertex v which must be stolen has degree greater than 1 in its tree, removing it disconnects the tree. To avoid this kind of situation, the subtree rooted at v is cut and only v is stolen. All the other vertices u of the subtree have their history cleaned and are considered again as free vertices, i.e. treeNode[u] = ∅.

State of the art: existing algorithms

In this section, we present algorithms related to k-connectivity and k-partitioning.

Computing k-connectivity

As we have seen in Section 2.4, the connectivity of a graph is equal to the size of its minimal vertex cut. The max-flow min-cut Theorem states that the maximum flow between to vertices is equal to the minimum cut to disconnect these two vertices. But if we use flow algorithm directly, do not compute the connectivity, since it will be possible to have two different flows passing through the same vertex.

So first the graph needs to be transformed. For this purpose, we need a capacity on the vertices. To do so each vertex is divided into two new vertices. Each incoming edge is attached to the first vertex and each leaving edge to the second vertex. Another edge is added between the two new vertices. The capacity of all edges of the graph is set to 1.

Then to find the connectivity, we compute the maximum flow between each pair of nodes and we keep only the lowest value. This value is the connectivity.

k-partitioning

In this section, we focus on the different existing k-partitioning algorithms.

First of all, since it has been proven that for some kinds of graphs finding a k-partition is an N P -hard problem [START_REF] Barth | A degree bound on decomposable trees[END_REF], finding a partition in a graph is N P -hard in general.

Data: G = (V, E) a graph Result: k the connectivity min = ∞; G = T ransf ormN ode(G); forall the u, v ∈ V, u = v, (u, v) / ∈ E do f = maximumF low(G , u, v); if f < min then min = f ; end end return min;
Algorithm 1: Computing the connectivity of a graph

As we mentioned earlier, it has been proven that, for a k-connected graph G, a k-partition always exists [START_REF] Győri | On division of graphs to connected subgraphs[END_REF][START_REF] Lovász | A homology theory for spanning trees of a graph[END_REF]. The algorithm from [START_REF] Ma | An o(k 2 n 2 ) algorithm to find a k-partition in a k-connected graph[END_REF] apart, no polynomial general algorithm, i.e. for all values of k, have been proposed. Polynomial algorithms have been proposed for k = 2[STN90] and k = 3 [START_REF] Wada | Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs[END_REF]. More recently, it has been proven in [START_REF] Shin Ichi Nakano | A linear-time algorithm for four-partitioning four-connected planar graphs[END_REF] that if G is a planar graph and if the roots of the partition are located on the same face of a plane embedding of G, there is a linear-time algorithm for k = 4.

Work

Tools

Generating k-connected random graphs

In order to test our implementation of the algorithm proposed in [START_REF] Ma | An o(k 2 n 2 ) algorithm to find a k-partition in a k-connected graph[END_REF], k-connected graphs had to be generated. We have implemented two methods, although the graphs produced are not uniformly randomised.

The first method is based on the vertex degree. To be k-connected, a graph needs to have vertices of degree at least k. For each vertex, edges are added until the vertex has degree at least k. Once this procedure achieved, then possibly the reduced graph is k-connected.

Since this first method is not deterministic, we have implemented another method which produces a k connected graph by creating several complete components and linking them together. The algorithm is described in Algorithm 2. First, the complete components are generated. Then k edges are added between the first and the second components, k edges are added between the second and the third ones and so on.

The edges between every pair of components are not randomly selected, otherwise it would be easy to diconnect the graph by removing less than k vertices. So we procede in the following way for adding the edges. Suppose that the vertices of each component are numbered from 1 to the order of the component. The edges between the vertex 1 of the first component and the vertex 1 of the second component are selected. The same process is repeated for the second vertices to the k-th vertices and then for the other components. At the end, the resulting graph is k-connected.

Calculating a sparse spanning subgraph

In order to reduce the execution time of the main algorithm, we had to implement another algorithm described in [START_REF] Nagamochi | A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph[END_REF].

This algorithm is called FOREST and takes a graph G = (V, E) as a parameter. The output is slightly more complicated since it does not simply return the sparse spanning subgraph. Instead, the algorithm returns an array A of set of edges. The size of the array returned is

|E(G)|. The graph induced by the set of edges

k i=1 E i is k-connected, if the connectivity of G is greater or equal to k.
The main difficulty about the implementation of this algorithm was the use of a specific data structure that allows an access to the maximum, an insertion and a deletion of an element with a constant amortized cost. Even if such a structure does not exist for any kind of utilisation, it is possible to create one which has all the required properties for this algorithm, since the utilisation is very specific and since an element has always an integer associated value that can grow only from 1 at each step.

Tests have been created and run in order to prove that the result of our implementation of the FOREST algorithm was corresponding to the main objective:

∀k, k ≤ K(G), K(V, k i=1 E i ) = k.
This test has been validated on simple graphs, but it has also been seen that our implementation did not produce the expected result if the input is a multigraph. We checked this property by following the algorithm on small multigraphs and this showed us that the problem was not coming from the implementation, but rather from the algorithm. Since we are working on simple graphs, this was not really a problem for our tests.

Implementing the algorithm

In order to facilitate the comprehension of the algorithm implementation and the debugging, we choose to present the different parts of the algorithm. While we were implementing it, we also noted that some lines where misplaced, breaking the coherency of the algorithm.

In order to have the same complexity as the one proved in the paper, we sticked to the same data structures. In order to accept graphs where vertices are not only integers, we added an HashMap, allowing an access in constant time to the index of a vertex.

In the library we were using, spanning graphs were not designed to be modified. We created our own basic class which was handling trees with the needed methods like cutting a tree on a specific vertex.

Criticism

Finding a counter-example

Once the main issues of the implementation of the algorithm were solved, we had still some issues with the algorithm falling in endless loops. Our investigations on this specific problem ended with the fact that the problem was coming from the algorithm and not from the implementation. This was ensured by verifying the validity of the execution of our algorithm step by step on these specific problematic instances.

Detailed example of a failed execution

We here present an example of an execution which fails with the algorithm described in [START_REF] Ma | An o(k 2 n 2 ) algorithm to find a k-partition in a k-connected graph[END_REF]. The input of the algorithm is as follows :

• G is the graph drawn in Figure 12,

• k = 2,
• roots = {e, a},

• partitionSize = {5, 7}.
In order to illustrate the status of the algorithm, edges which are included in a tree have a stronger thickness, while both edges and vertices are colored according to the tree they belong to. Additionally, an array is presented under each graph, showing the content of the tree-node array which is used by the algorithm to choose which action has to be executed. During the first two steps, each partition needs to acquire more vertices, so each one grows by adding all the available neighborhood. At step 4, the tree rooted at a cannot be simply extended, since every adjacent vertex belongs to the other tree. The adjacent free vertices are f and g. Both respect the conditions necessary to allow the swapping. According to the algorithm, the vertex to swap must have the lowest degree in the concerned tree among the swappable candidates. It cannot be g since it has a higher internal degree than f in the concerned tree. The swapped vertex is then f . At step 5, the tree rooted at e must get one vertex back, since the other tree has taken one of its vertices. The two free candidates are i and k. Since only one is missing, only one must be added. In our case, i is added. At step 6, the tree rooted at a has no available adjacent vertex, it then has to swap a vertex among the neighborhood: e,g,h,i. e is not an option since it is the root of the other tree. Since g has an internal degree of 2, it cannot be choosen since h and i have an internal degree of 1. The swapped vertex is then h or i. Since nothing in the algorithm determines which one must be chosen, h might be swapped at that step. At step 8, the tree rooted at a must take a last vertex but, since it has no available adjacent vertex, it must then take a vertex from the tree rooted at e. The swappable vertices are g and i. Since they both have the same internal degree in the concerned tree, g can be choosen as a valid choice for the extension.

By swapping with g, the subtree rooted at g must be cut from the tree rooted at e. All the removed vertices (i,j,k) are then set back as unexplored, but not the swapped vertex g. After step 8, we are in a situation where the algorithm is stucked in a dead-loop. The tree rooted at a has the right amount of vertices, and steps concerning this tree will not produce any modification. The tree rooted at e cannot expand anymore, because all the adjacent vertices have already belong to him3 and have not been reset4 .

Counter-example in general case

In order to ensure that k = 2 is not a specific case for which the algorithm presented in [START_REF] Ma | An o(k 2 n 2 ) algorithm to find a k-partition in a k-connected graph[END_REF] can loop endlessly, we present a proof that an execution can loop endlessly for any k.

The proof is by induction. Since we have already exhibited a counter-example for k = 2, we only need to prove the induction step.

Let G be a k-connected graph for which the algorithm has a probability of looping endlessly strictly greater than 0 for the entry {r 1 , r 2 , . . . , r k } and {n 1 , n 2 , . . . , n k }. Then a graph G can be found such that G is k + 1-connected and there exists an entry for which the algorithm has a probability of looping endlessly strictly greater than 0.

Proof: If we create G by adding a new vertex v connected to every vertex of G, i.e.

V (G ) = V (G) ∪ v and E(G ) = E(G) ∪ u∈V (G)
{u, v}, it is obvious that G is k + 1-connected, since every minimal vertex cut of G needs to have one additional vertex in order to be a cut of G .

An execution of the algorithm with G , {r 1 , r 2 , . . . , r k , v}, {n 1 , n 2 , . . . , n k , 1} as input has a probability of looping endlessly strictly greater than 0, as the introduced vertex v has no influence since the associated tree is full since the beginning and the new edges are not useable.

Improvements

Vertex selection condition

To select the vertex to swap between two trees, the article algorithm bases its choices on the vertex degree. As we have seen before, the selection of specific vertices can lead to an endless loop. Choosing the vertex with the lowest degree can cut a long branch of the tree, whereas select another vertex with a greater degree removes less vertices to the tree.

That is why, we have modified the vertex selection condition. Rather than basing the selection condition on the vertex degree, we base it on the number of descendants. So, when a vertex is swapped the minimum number of vertices is removed from the tree. This modification allows to avoid the endless loop for the counter-example presented above. However there are still some executions on other graphs which are falling into endless loops.

Detecting endless loops

A counter-example which shows that the algorithm can fall in endless loops have been exhibited. This raises one question: is it possible to detect when there is an endless loop? An improvement has been added to the algorithm in order to detect such situations. To do so, we save the last root index where we have added or swapped a vertex. If the saved index is equal to the current root index and no vertex have been added or swap then it means that the algorithm has entered in an endless loop. Then the execution is stopped.

Conclusion

Through this study, we have demonstrated that the algorithm proposed in [START_REF] Ma | An o(k 2 n 2 ) algorithm to find a k-partition in a k-connected graph[END_REF] is not correct, for any k. The private communication from E. Győri mentioned in [START_REF] Shin Ichi Nakano | A linear-time algorithm for four-partitioning four-connected planar graphs[END_REF] has been prooved with a counter-example, exhibiting the possibility of the algorithm to fall into endless loops. Then the property was extended to any k with an inductive proof.

The counter-example was found by implementing the algorithm and running it on randomly generated graphs. Therefore, the tools implemented can be used to test new approaches similars to the algorithm or needing the generation of k-connected graphs.

Since we prooved that the algorithm proposed in [START_REF] Ma | An o(k 2 n 2 ) algorithm to find a k-partition in a k-connected graph[END_REF] is not correct, there is still no polynomial solutions that solve the k-partition problem for any k. Even if algorithms have been proposed which find a solution to this problem for specific value of k or for specific kinds of graph.

We proposed a modification which allows to avoid endless loops, informing of a failure if the execution would have lead to an endless loops. This specific modification could allow to create a Las Vegas algorithm if the probability that the algorithm returns successfully the solution is equal or greater than 1 2 . Prooving this would not bring a polynomial solution to the k-partition problem, but it would already proove that the k-partition problem is in ZP P .

Figure 1 :V

 1 Figure 1: An undirected simple graph with 5 vertices and 4 edges

Figure 2 :V

 2 Figure 2: A directed simple graph with 5 vertices and 4 edges

Figure 3 :

 3 Figure3: A graph and one of its subgraphs (in green)

Figure

  Figure 4: A tree

Figure 5 :

 5 Figure5: A graph and one of its spanning trees (in green)

Figure 7 :

 7 Figure7: A graph and one of its cut-sets (in green)

Figure 8 :

 8 Figure 8: A 2-connected graph and one of its articulation sets (in green)

Figure

  Figure 9: A flow network

Figure 10 :

 10 Figure 10: A 3-partition (in red, green and puple) of a graph

Figure 11 :

 11 Figure 11: Input and output of the k-partition problem

  Data: k the connectivity, N the number of components, n the size of componentsResult: A k-connected graph components = ∅; edges = ∅; for i = 1 to N do components = components ∪ newCompleteComponent(n) end for i = 1 to N-1 do for j = 1 to k do edges = edges ∪ (components[i][j], components[i + 1][j]) end end g = newGraph(components, edges); return g; Algorithm 2: k-connected graph generator

Figure

  Figure 12: Failed Execution : Initial graph

FigureFigure

  Figure 13: Failed Execution : Step 1

Figure

  Figure 15: Failed Execution : Step 3

Figure

  Figure 16: Failed Execution : Step 4

Figure

  Figure 17: Failed Execution : Step 5

Figure

  Figure 18: Failed Execution : Step 6

Figure

  Figure 19: Failed Execution : Step 7

Figure

  Figure 20: Failed Execution : Step 8

See

2.2

See 2.4

See line 28 of the algorithm

See line 47 of the algorithm