text:
Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

The epidemiology, radiology and biological characteristics of interval breast cancers in population mammography screening

Abstract

An interval breast cancer is a cancer that emerges following a negative mammographic screen. This overview describes the epidemiology, and the radiological and biological characteristics of interval breast cancers in population mammography screening. Notwithstanding possible differences in ascertainment of interval breast cancers, there was broad variability in reported interval breast cancer rates (range 7.0 to 49.3 per 10,000 screens) reflecting heterogeneity in underlying breast cancer rates, screening rounds (initial or repeat screens), and the length and phase of the inter-screening interval. The majority of studies (based on biennial screening) reported interval breast cancer rates in the range of 8.4 to 21.1 per 10,000 screens spanning the two-year interval with the larger proportion occurring in the second year. Despite methodological limitations inherent in radiological surveillance (retrospective mammographic review) of interval breast cancers, this form of surveillance consistently reveals that the majority of interval cancers represent either true interval or occult cancers that were not visible on the index mammographic screen; approximately 20–25% of interval breast cancers are classified as having been missed (false-negatives). The biological characteristics of interval breast cancers show that they have relatively worse tumour prognostic characteristics and biomarker profile, and also survival outcomes, than screen-detected breast cancers; however, they have similar characteristics and prognosis as breast cancers occurring in non-screened women. There was limited evidence on the effect on interval breast cancer frequency and outcomes following transition from film to digital mammography screening.

Introduction

Aims

A breast cancer (BC) that emerges following a negative mammographic screen is referred to as an interval BC.1 In this overview, we describe the epidemiology, radiology and biological characteristics of interval BCs in population mammography screening, highlighting published research from the most recent decade. The aims of the review were to provide an update on interval BCs that extends both our work on radiological surveillance of interval BCs1 and that from other researchers that have quantified interval BC rates,2,3,4 to elucidate evidence on interval BCs following transition to digital mammography screening, and to identify knowledge gaps that warrant further research.

Background and definitions

An interval BC refers to a cancer that presents after a ‘normal’ screening mammogram and before the next scheduled mammogram, in other words a BC that arises or is diagnosed in the inter-screening interval [see also Fig. 1].1 This definition may be qualified by specifying an interval case as an invasive BC,5 given that the vast majority of interval cases are invasive malignancies and much of the routinely reported data on interval BC rates is based on invasive BC. In addition, some qualify the definition further by specifying that interval BCs are those that arise clinically2, 5 in the inter-screening interval—although that would be the likely presentation for almost all interval BCs it should be noted that a BC identified in the inter-screening interval would still be classified as such irrespective of how it came to be diagnosed. Factors that have been associated with increased risk of an interval BC in screened women include high mammographic breast density,6,7,8 current use of hormone replacement therapy,8, 9 young relative to older age (partly reflecting confounding from breast density), however, absolute incidence rates are higher in older women given higher underlying BC rates,8 previous false-positive mammography,10 and a family history of BC.8, 10, 11

Because interval BCs are representative of the sensitivity of population breast screening, and given that they are an adverse outcome for women partaking in screening, surveillance of interval BCs is routinely practiced in many screening programs. Surveillance comprises epidemiologic measures (such as interval BC rates)1, 3 to monitor the frequency of interval cases, and may be complemented by radiological surveillance as part of quality assurance in organised screening programs.1 Various methodological and analytic parameters can substantially influence estimates of interval BC rates and other epidemiologic measures of interval BCs, as highlighted by several investigators.3, 12 These include variability in the definition of an interval BC (whether based on invasive BC or whether ductal carcinoma in-situ (DCIS) cases are included); whether false-negative assessment cases and lapsed attenders are counted or excluded; the adequacy of ascertainment of interval cancers, hence also the adequacy of cancer notification and registration; and the duration of follow-up for ascertainment of cases.3, 12 Importantly, underlying BC rates or burden in the population also affects interval BC rates. For these reasons, epidemiologic measures of interval BCs are best suited for monitoring within screening services or programs because comparisons between screening programs and countries is limited by heterogeneity in the above-described variables that affect quantitative estimates of interval BCs.

Radiological surveillance is a qualitative form of surveillance that defines and measures the extent that interval BCs represent screen-reading ‘errors’ as opposed to being non-detectable cancers at mammography screening. Radiological surveillance entails review of the mammograms taken at the time the interval BC is identified (usually at clinical presentation, hence the diagnostic mammograms) and the pre-diagnosis mammographic screen (the ‘negative’ index screen) and an interpretative judgement to classify each case into pre-defined categories.1, 13,14,15 These categories may vary in definition, however, most include a ‘true interval’ category (where the cancer is not visible at the index screen but becomes visible at the diagnostic mammogram) and a ‘missed’ interval BC being the equivalent of a false-negative (where the cancer is visible on the index mammogram but is not recalled or is misinterpreted) and is at times referred to as screening error.1, 13,14,15 Various methods have been used to perform radiological surveillance, as described in a review by Houssami et al.1 with potential biases inherent in the review strategy and the extent that readers are informed that they are evaluating interval BC cases.1 Notwithstanding the methodological limitations of radiological surveillance, it provides insights into screening quality and on how screening could be improved.

In the present review, we consider both epidemiological and radiological aspects of interval BCs, and complement these with information on tumour prognostic characteristics of interval BCs, to define common themes as well as evidence gaps, to enhance our understanding of interval BCs and inform research priorities.

Results

Epidemiologic surveillance

Table 1 presents a summary of epidemiologic measures for interval cancers including interval BC rates, which were the most commonly reported estimates for routine screening monitoring.4, 13, 15,16,17,18,19,20,21,22,23,24,25,26,27,28,29 The table highlights the broad variability in both interval BC rates and cancer detection rates at screening, both of which are partly driven by underlying cancer rates in the populations reported in these studies. There is wide variability in the overall interval BC rates, ranging between 7.0 and 49.3 per 10,000 screens, partly explained by data shown for screening rounds (initial and repeat screens) and the duration and year of the inter-screening intervals; where reported, data for the inter-screening interval are presented by yearly rates for biennial or triennial screening. If restricted to studies of annual screening or to year 1 data from biennial screening programs, there is evidence that interval BC rates are consistently <8/10,000 screens. The majority of studies in Table 1 report data for biennial screening programs: the interval BC rates spanning the two years between screens are within the range of 8.4 to 21.1 per 10,000 screens, with the larger proportion of the estimated interval BC rates occurring in the second year of a two-yearly interval. The evidence also consistently shows that interval BC rates are higher at repeat (incident) rounds than initial (prevalent) screening rounds.

For the majority of studies (based on biennial screening) interval BCs represent around 17–30% of the cancers occurring in screening participants as summarised in the simple proportion in the last column of Table 1; that proportion is relatively lower for annual (14.7% based on one study) and higher for triennial (32–38%) screening intervals. The proportional interval BC rate, also shown in Table 1, is not reported by all studies because this measure requires estimating the expected underlying incidence in the absence of screening, so may not be feasible to calculate in contemporary screening practice.2

Mammography screening interventions associated with reduction in interval BC rates

A study conducted in the United Kingdom’s screening program, based on women aged 50–64 screened between 2003 and 2005, reported that two-view mammography (at the last routine screen) was associated with a reduction in interval BC rates of 6.8/10,000 screens compared with one-view mammography.30 The investigators concluded that this suggests that two-view (instead of one-view) mammography at incident screening was accompanied by a 15–20% reduction in interval BC rates. An earlier study by Seigneurin et al.27 reported similar evidence from the French population breast screening program, based on women aged 50–69, in a comparison of two time frames reflecting transition from one-view to two-view mammography: a reduction of 8.6 interval BCs per 10,000 screens was associated with two-view mammography, with an estimated 36% difference in relative risk of interval BC at 24 months for two vs. one view mammography (Table 1). Weber et al.13 reported a study of the Southern screening region of the Dutch program, in which the use of digital (compared to film-screen) mammography was shown to be associated with a modest but significant reduction in interval BC rates of 3/10,000 screens (p = 0.02; Table 1).

As shown in Table 2, radiological categories varied slightly across studies, however, most studies reported the distribution for true interval BC and also for missed or false-negative cases (defined in the introduction); some studies reported the additional categories of ‘occult’ and ‘minimal-signs’ interval BCs (see Table 2 footnote). The evidence table shows that the vast majority of interval BCs were not missed at screen-reading but were true interval BCs (range 40% to 77%) or occult interval BCs (7% to 32%), meaning that they were not visible on the index screen even in hindsight. Of note, some of the high proportions reported for true interval BCs (>60%) appear to have included the occult cases among the true interval cases. The proportion of missed (false-negative) interval BCs ranged between 13.6% and 35%, with the majority reporting a frequency of 20–25% based on radiological surveillance. A study from Ciatto and colleagues33 used a multi-methods evaluation of the same set of mammograms, and showed that increasing the information available to screen-readers significantly increased the proportion of interval BCs classified as missed (Table 2), highlighting the impact of review methods on radiological classification.

Additional findings summarised in Table 2 describe radiological findings (where present) for the index screen, which were frequently masses or asymmetric densities. They also highlight study-specific data showing differences in the variables associated with interval BCs, and in the tumour characteristics of interval BCs, across radiological categories derived from mammographic review.

Radiological review of interval BCs following screening with digital or film-screen mammography was reported by Knox et al.42 showing that a similar proportion of cancers were classified as missed cases at digital and film-screen (10.5% and 8.1%, respectively, p = 0.77). However, fewer interval BCs were depicted as microcalcifications alone or in association with another imaging abnormality following digital than film-screen mammography (16% and 32%, respectively, p = 0.02) (ref. 42). Nederend and colleagues38 investigated interval BCs in a population-based study of regional screening units in the Netherlands, and showed that significantly more interval BCs were classified as true-negative or true interval cases (not visible at the index screen) at radiological review of prior digital than prior film-screen mammography (65.3% vs. 47.1%, p = 0.02) as shown in Table 2; otherwise, there were no differences between interval BCs at digital or film-screen in terms of mammographic abnormalities at the prior screen or in tumour characteristics. Generally similar findings were reported by Weber et al.13 also from the Dutch screening program, who additionally observed that interval BCs emerging in year 2 of the inter-screen interval for digital mammography were more frequently true (than missed) interval cancers compared to those for film-screen mammography (p = 0.03; Table 2).

Biological characteristics and prognosis

Table 3 summarises biological findings including tumour characteristics and biomarker profile for interval BCs, and outlines the comparison reported in each study because that accounts for some of the apparent heterogeneity in results.11, 13, 14, 26, 31, 35,36,37, 39, 43,44,45,46,47,48 For the majority of studies, which compared interval BCs with screen-detected cancers, there were consistent findings that interval BCs had worse prognostic features, such as larger tumour size, higher frequency of node metastases, higher histologic grade, and more advanced disease compared to screen-detected BC (Table 3). Although biomarker data were not consistently reported in these studies, where reported there was evidence that interval BCs had a higher frequency of triple-negative or HER2-positive cancers and a lower frequency of hormone receptor-positive cancers than screen-detected BC (Table 3).

Some studies compared prognostic features between radiological categories of interval BCs, with variable findings (and limited statistical comparisons once study data were examined in subsets), however, some differences were noted between radiological subgroups. These differences by radiological subgroup are detailed in Table 3, and suggest that the ‘missed’ group had worse prognostic features than the true interval and occult interval cancers, except for tumour grade, which was reported to be more frequently higher for true interval and occult interval BCs than missed cases. Additional findings suggest that these outcomes may differ slightly between dense and non-dense breasts but density-specific findings were reported in very few studies (Table 3).

In the limited number of studies comparing interval BCs with clinically presenting cancers in non-screened women,44, 46 there was evidence that interval cancers were similar in terms of prognostic features to the BCs occurring in non-screened women, however, one study reported that interval BCs had slightly higher proportions of larger tumours (>20 mm) than BCs in non-screened women.46

Prognosis of interval BC

A population-based cohort study found similar survival for women who had an interval BC in the Norwegian screening program (hazard ratio (HR) 0.98; 95% confidence interval 0.84–1.15) as those who had BC diagnosed in the same time frame but had not yet been invited to mammography screening (non-screened women).46 A study from the Malmo mammography screening program49 showed that interval BCs from the first decade of service screening had similar stage distributions and survival as the BCs diagnosed in non-attenders to screening, whereas the screen-detected cancers in that time frame had more favourable stage distributions and survival than the interval cases. In this same study, there was also evidence that the prognosis of women with interval BC had improved over a 20-year period, as may be expected from overall improvements in BC prognosis over time.

Domingo and colleagues14, 50 conducted several studies examining the characteristics of interval BCs; one of these evaluated 2245 invasive BCs and clearly showed that interval BCs had more advanced tumours than screen-detected BCs (additional details by interval BC category shown in Table 3).14 In an earlier study of 228 invasive BCs diagnosed among Barcelona women aged 50–69 years, Domingo et al.50also found that disease-free survival rates (at 5 year follow-up from diagnosis) for screen-detected, true interval, and symptom-detected BC were 87.5%, 64.1%, and 79.4%, respectively, and overall survival rates were 94.5%, 65.5%, and 85.6%, respectively.50 In keeping with these findings, they concluded that clinically-detected BC especially where these are true interval cancers had worse prognosis and poorer survival than screen-detected BC even after adjustment for clinical-pathological variables.50 Porter and colleagues48 compared the features of interval BCs by radiological classification, and although they observed differences in the histological characteristics (shown in Table 3) there was no significant survival difference between interval BC radiological types (p = 0.64).

Some studies have examined the prognostic characteristics of interval BCs by breast tissue density.11, 45 Holm et al.45 showed that interval BCs occurring in non-dense breasts (defined by<20% density) had poorer prognostic features than screen-detected BC (Table 3), whereas interval BCs in dense breasts (≥50% density) were phenotypically more similar to screen-detected cancers. Eriksson et al.51 compared survival in interval and screen-detected BC allowing for mammographic density in women aged 50 years and older; they showed that hazard rates for BC-specific survival were significantly higher for interval than for screen-detected cancers, independent of density. In addition, interval BC in women with non-dense breasts had increased 5-year survival HR (2.43, p = 0.001) compared to screen-detected BC in non-dense breasts, but this was not the case in women with dense breasts, in whom a difference in survival was not statistically evident between interval and screen-detected BC (5-year survival HR 1.41, p = 0.49) after adjustment for cancer size.51

Discussion

This overview of the epidemiological, radiological, and tumour characteristics of interval BCs—cancers that emerge following a negative mammographic screen—highlights key themes on interval BCs, which are summarised in Fig. 2. Interval BCs are an important consideration in population BC screening because they are indicative of screening quality hence evaluating these cancers may help identify areas for potential improvement, and because they represent a failure of screening to detect a BC that subsequently progresses to presentation. It is clear from radiological surveillance data summarised in our work that these cancers are not necessarily missed at mammography screening, with most studies reporting around 20–25% of interval BCs to be missed (false-negative) cases. While radiological surveillance has limitations inherent in retrospective re-interpretation of imaging, and radiological classification of interval BCs is affected by the methodology used to perform mammographic review (Table 2), quantitative evidence shows that the majority of interval cancers are true interval or occult interval BCs that were not visible on the index screen. It should be acknowledged that radiological surveillance is not practiced in all screening settings, and the aim of summarising the evidence is not to advocate this form of surveillance, rather its findings can inform practice. For example, it seems likely that enhancing screen-reader skills would have relatively less effect in controlling interval BCs than, say, enhancing mammography technology or using alternate or additional technology to address the majority of cases that are not visible at the index mammography screen even in hindsight.

Epidemiological monitoring of interval BC rates is a more widely performed surveillance in population mammography screening programs. Variability in the overall interval BC rates shown in Table 1 reflects the underlying BC risk in the population (which is also glimpsed in study-specific BC detection rates), the mix of initial and repeat screen rounds, and the length of the inter-screening interval. The variability due to the inter-screening interval is particularly evident where data are presented by yearly rates for biennial or triennial screening: our summary shows consistent evidence that rates in year 2 are at least twice those in year 1 (Table 1). The majority of studies in the evidence table report data from biennial screening, and show that interval BCs represent roughly one quarter of the cancers occurring in screening participants—that proportion is lower for annual, and higher for triennial, screening intervals. These findings should not be taken to infer that annual screening has better population outcomes than biennial screening (in fact biennial screening reduces some screening harms compared to annual screening), they merely highlight that many interval BCs are identified in the second year of a biennial screening round, and is commensurate with the pattern of findings from radiological surveillance specifically that many interval BCs are true interval cancers. Additional data from radiological surveillance from Weber and colleagues13 indicates that the proportion of interval cancers that are true interval BCs increases in year 2 (relative to year 1) at biennial screening. The evidence table also shows that interval BC rates are higher at repeat (incident) rounds than initial (prevalent) screening rounds within the same screening setting and population. This finding has not been thoroughly explained in the reviewed studies but is presumably due to age increase and a tendency for lower recall rates at repeat screening of the same women but warrants further research.

Although there is a substantial body of knowledge on interval BC rates in mammography screening, as shown in Table 1, there was little direct evidence on mammography-based interventions that reduce interval BC rates. A limited number of studies identified in this review reported that two-view (vs. one-view) mammography was associated with significant reductions in interval BC rates in population-based programs.27, 30 There was little evidence on the effect of digital mammography on interval BC rates, limited to one study showing that the use of digital (compared to film-screen) mammography was associated with a small but significant reduction in interval BC rates.13

Evidence on radiological features of interval BCs following transition to digital mammography was also limited to few studies13, 38, 42 with one study suggesting that implementation of digital mammography modified the mammographic pattern of interval BCs, with fewer interval BCs depicted as microcalcifications.42 However, two studies did not find substantial differences in interval BCs, in terms of the pattern of mammographic findings, following transition to digital mammography.13, 38

Studies providing data on the biological characteristics of interval BCs have mostly compared them to screen-detected BCs from the same screening setting and population, and have shown that interval BCs have relatively worse tumour prognostic characteristics, and worse survival outcomes, than screen-detected BCs. Interval BCs were consistently reported to be at a more advanced stage when diagnosed compared to screen-detected BC in terms of larger tumour size, higher frequency of node metastases, higher histologic grade, and had less favourable biomarker profile including a higher frequency of triple-negative cancers. This does not mean that interval BCs are an aggressive group of cancers, in fact they have tumour characteristics and survival outcomes that approximate those of BCs diagnosed in non-screened women, based on data from the few studies reporting that comparison.44, 46 One study reported that interval BCs had higher proportions of larger tumours than BCs in non-screened women but did not find any difference in survival between these groups.46 Further insights were provided by studies comparing prognostic features between radiological categories of interval BCs, with findings suggesting that the ‘missed’ group had worse prognostic features for tumour size and node status (possibly due to the delay in detection) than the true interval and occult interval BCs although the latter were more likely to have higher tumour grades (suggesting these to be more rapidly growing cancers representing new events on the mammogram).

Because mammographic breast density is an established risk factor for interval BC in screened women,6, 7 some of the studies summarised in this review evaluated interval BCs in relation to mammographic density.10, 11, 14, 39, 45, 51 The detailed findings, summarised in our results, are complex but reveal some common findings. Mammographic density was consistently associated with occult BCs (followed by true interval BCs) rather than missed interval cases,10, 14 highlighting a likely masking effect. In addition, there was a suggestion that interval BCs occurring in non-dense breasts may be associated with worse prognostic features and outcomes,45, 51 perhaps reflecting that interval BCs in non-dense breasts were more likely to be newly arising cases associated with rapid growth—however, the data were from few studies.

Epidemiological and radiological surveillance of interval BCs, complemented by an understanding of the biology of these cancers, provide insights into ‘how often’ and ‘why’ screening may not detect a BC that is subsequently diagnosed. Evidence shows that quantitative data on interval BCs are very heterogeneous and are influenced by several factors including the length of the inter-screening interval. Most published studies have reported data from biennial screening practice and in that context interval BCs represent roughly 17–30% of the cancers occurring in screening participants. Radiological surveillance highlights that the majority of interval BCs represent true interval or occult interval BCs that were not visible on the index mammographic screen, with only around 20–25% of interval BCs reported to have been missed cases on mammographic review. Biological characteristics of interval BCs show that they have relatively worse tumour prognostic characteristics and survival outcomes than screen-detected BCs, but similar characteristics and prognosis to BCs occurring in non-screened women. There was limited evidence of the effect on interval BC frequency and outcomes following transition from film to digital mammography screening.

Methods

This is a descriptive review based on a literature search and extraction of relevant information into evidence tables for each of three themes: epidemiologic measures, radiological surveillance and biology of interval cancers in population mammography screening.

Literature search

Relevant publications were identified through a Medline literature search: we exploded the term ‘breast neoplasms’ to August 2016, and combined this with title-searching for ‘interval cancer$’ or ‘interval breast cancer$’. Study identification focused on published work from 2006 onwards, given the above-stated aims of the review and the time frame from our previous evidence review,1 however, earlier studies were considered where data were reported in more recent publications.2, 4 Studies that provided information on population mammography screening allowing contribution into the evidence tables were included. Additional relevant studies were included in descriptive text if they provided key information on interval BCs that was not captured in the evidence table format. Studies that screened groups at increased risk of BC were not within the scope of the present review. Appendix 1 shows a flow diagram of the literature search and study inclusion process.

Evidence tables

Each evidence table provided a summary of key findings from each study contributing information on interval BCs into at least one of three themes: epidemiologic measures, radiological surveillance and biologic features. For the evidence table on epidemiological measures (Table 1), studies were included if they reported data on interval BC rates (overall, or by year of inter-screen interval or by screening round) and also cancer detection rates because the latter provide complementary information about the study population and screening sensitivity. For the table on radiological surveillance (Table 2), studies were included if a radiological review and categorisation was performed allowing reporting of data on the frequency of one or more categories of interval BCs, and at minimum reporting data on false-negative (missed) interval cases. The evidence table on biological characteristics of interval BCs (Table 3) summarised data on tumour prognostic features, and also biomarkers where reported.

References

1. Houssami, N., Irwig, L. & Ciatto, S. Radiological surveillance of interval breast cancers in screening programmes. Lancet Oncol. 7, 259–265 (2006).

2. Andersen, S. B., Tornberg, S., Lynge, E., Von Euler-Chelpin, M. & Njor, S. H. A simple way to measure the burden of interval cancers in breast cancer screening. BMC Cancer 14, 782 (2014).

3. Bulliard, J. L. et al. Methodological issues in international comparison of interval breast cancers. Int. J. Cancer 119, 1158–1163 (2006).

4. O’Brien, K. M., Dwane, F., Kelleher, T., Sharp, L. & Comber, H. Interval cancer rates in the Irish national breast screening programme. J. Med. Screen. 22, 136–143 (2015).

5. Bucchi, L. et al. Incidence of interval breast cancers after 650,000 negative mammographies in 13 Italian health districts. J. Med. Screen. 15, 30–35 (2008).

6. Boyd, N. F. et al. Mammographic density and the risk and detection of breast cancer. N. Engl. J. Med. 356, 227–236 (2007).

7. Kerlikowske, K. et al. Identifying women with dense breasts at high risk for interval cancer: a cohort study. Ann. Intern. Med. 162, 673–681 (2015).

8. Lowery, J. T. et al. Complementary approaches to assessing risk factors for interval breast cancer. Cancer Causes Control 22, 23–31 (2011).

9. Chiarelli, A. M. et al. Influence of patterns of hormone replacement therapy use and mammographic density on breast cancer detection. Cancer Epidemiol. Biomarkers Prev 15, 1856–1862 (2006).

10. Blanch, J. et al. Impact of risk factors on different interval cancer subtypes in a population-based breast cancer screening programme. PLoS ONE 9, e110207 (2014).

11. Boyd, N. F. et al. Mammographic features associated with interval breast cancers in screening programs. Breast Cancer Res 16, 417 (2014).

12. Hofvind, S., Yankaskas, B. C., Bulliard, J. L., Klabunde, C. N. & Fracheboud, J. Comparing interval breast cancer rates in Norway and North Carolina: results and challenges. J. Med. Screen. 16, 131–139 (2009).

13. Weber, R. J. et al. Characteristics and prognosis of interval cancers after biennial screen-film or full-field digital screening mammography. Breast Cancer Res. Treat. 158, 471–483 (2016).

14. Domingo, L. et al. Tumor phenotype and breast density in distinct categories of interval cancer: results of population-based mammography screening in Spain. Breast Cancer Res 16, R3 (2014).

15. Carbonaro, L. A. et al. Interval breast cancers: absolute and proportional incidence and blinded review in a community mammographic screening program. Eur. J. Radiol. 83, e84–e91 (2014).

16. Bennett, R. L., Sellars, S. J. & Moss, S. M. Interval cancers in the NHS breast cancer screening programme in England, Wales and Northern Ireland. Br. J. Cancer. 104, 571–577 (2011).

17. Bordas, P., Jonsson, H., Nystrom, L. & Lenner, P. Interval cancer incidence and episode sensitivity in the Norrbotten mammography screening programme, Sweden. J. Med. Screen. 16, 39–45 (2009).

18. Fong, Y. et al. The incidence and 10-year survival of interval breast cancers in Wales. Clin. Radiol. 69, e168–e172 (2014).

19. Fracheboud, J. et al. Interval cancers in the Dutch breast cancer screening programme. Br. J. Cancer. 81, 912–917 (1999).

20. Heidinger, O. et al. The incidence of interval cancers in the German mammography screening program: results from the population-based cancer registry in North Rhine-Westphalia. Dtsch. Arztebl. Int 109, 781–787 (2012).

21. Henderson, L. M. et al. Breast cancer characteristics associated with digital versus film-screen mammography for screen-detected and interval cancers. AJR. Am. J. Roentgenol. 205, 676–684 (2015).

22. Hofvind, S., Geller, B., Vacek, P. M., Thoresen, S. & Skaane, P. Using the European guidelines to evaluate the Norwegian Breast Cancer Screening Program. Eur. J. Epidemiol. 22, 447–455 (2007).

23. Kellen, E. et al. Interval cancers in the beginning years of the breast cancer screening programme in the Belgian province of Limburg. Acta Clin. Belg. 63, 179–184 (2008).

24. Lynge, E. Mammography screening for breast cancer in Copenhagen April 1991-March 1997. mammography screening evaluation group. APMIS Suppl 83, 1–44 (1998).

25. Njor, S. H. et al. Mammography screening in the county of Fyn. November 1993-December 1999. APMIS Suppl 110, 1–33 (2003).

26. Renart-Vicens, G. et al. Evaluation of the interval cancer rate and its determinants on the Girona Health Region’s early breast cancer detection program. BMC Cancer 14, 558 (2014).

27. Seigneurin, A., Exbrayat, C., Labarere, J. & Colonna, M. Comparison of interval breast cancer rates for two-versus single-view screening mammography: a population-based study. Breast 18, 284–288 (2009).

28. Tornberg, S. et al. A pooled analysis of interval cancer rates in six European countries. Eur. J. Cancer Prev. 19, 87–93 (2010).

29. Vettorazzi, M. et al. Quality control of mammography screening in the Veneto Region. Evaluation of four programs at a local health unit level--analysis of the frequency and diagnostic pattern of interval cancers. Tumori 92, 1–5 (2006).

30. Dibden, A. et al. Reduction in interval cancer rates following the introduction of two-view mammography in the UK breast screening programme. Br. J. Cancer 110, 560–564 (2014).

31. Bare, M. et al. Interval breast cancers in a community screening programme: frequency, radiological classification and prognostic factors. Eur. J. Cancer Prev. 17, 414–421 (2008).

32. Caumo, F. et al. Analysis of interval cancers observed in an Italian mammography screening programme (2000-2006). Radiol. Med. 114, 907–914 (2009).

33. Ciatto, S. et al. Interval breast cancers in screening: the effect of mammography review method on classification. Breast 16, 646–652 (2007).

34. Pirola, M. E. et al. Quality of mammography screening in the Milan programme: evidence of improved sensitivity based on interval cancer proportional incidence and radiological review. Breast 18, 208–210 (2009).

35. Evans, A. J. et al. Radiological and pathological findings of interval cancers in a multi-centre, randomized, controlled trial of mammographic screening in women from age 40-41 years. Clin. Radiol. 62, 348–352 (2007).

36. Gao, F., Chia, K. S., Ng, F. C., Ng, E. H. & Machin, D. Interval cancers following breast cancer screening in Singaporean women. Int. J. Cancer 101, 475–479 (2002).

37. Hofvind, S., Geller, B. & Skaane, P. Mammographic features and histopathological findings of interval breast cancers. Acta Radiol. 49, 975–981 (2008).

38. Nederend, J. et al. Impact of the transition from screen-film to digital screening mammography on interval cancer characteristics and treatment - a population based study from the Netherlands. Eur. J. Cancer 50, 31–39 (2014).

39. Payne, J. I., Caines, J. S., Gallant, J. & Foley, T. J. A review of interval breast cancers diagnosed among participants of the Nova Scotia breast screening program. Radiology 266, 96–103 (2013).

40. Pellegrini, M. et al. Analysis of proportional incidence and review of interval cancer cases observed within the mammography screening programme in Trento province, Italy. Radiol. Med. 116, 1217–1225 (2011).

41. Gordon, P. B., Borugian, M. J. & Warren Burhenne, L. J. A true screening environment for review of interval breast cancers: pilot study to reduce bias. Radiology 245, 411–415 (2007).

42. Knox, M. et al. Impact of full field digital mammography on the classification and mammographic characteristics of interval breast cancers. Eur. J. Radiol. 84, 1056–1061 (2015).

43. Caldarella, A. et al. Biological characteristics of interval cancers: a role for biomarkers in the breast cancer screening. J. Cancer Res. Clin. Oncol. 139, 181–185 (2013).

44. Caumo, F. et al. Interval cancers in breast cancer screening: comparison of stage and biological characteristics with screen-detected cancers or incident cancers in the absence of screening. Tumori 96, 198–201 (2010).

45. Holm, J. et al. Risk factors and tumor characteristics of interval cancers by mammographic density. J. Clin. Oncol. 33, 1030–1037 (2015).

46. Kalager, M., Tamimi, R. M., Bretthauer, M. & Adami, H. O. Prognosis in women with interval breast cancer: population based observational cohort study. BMJ 345, e7536 (2012).

47. Meshkat, B. et al. A comparison of clinical-pathological characteristics between symptomatic and interval breast cancer. Breast 24, 278–282 (2015).

48. Porter, G. J. et al. Interval breast cancers: prognostic features and survival by subtype and time since screening. J. Med. Screen. 13, 115–122 (2006).

49. Zackrisson, S., Janzon, L., Manjer, J. & Andersson, I. Improved survival rate for women with interval breast cancer—results from the breast cancer screening programme in Malmo, Sweden 1976-1999. J. Med. Screen. 14, 138–143 (2007).

50. Domingo, L. et al. Aggressiveness features and outcomes of true interval cancers: comparison between screen-detected and symptom-detected cancers. Eur. J. Cancer Prev. 22, 21–28 (2013).

51. Eriksson, L. et al. Mammographic density and survival in interval breast cancers. Breast Cancer Res 15, R48 (2013).

Acknowledgements

N. Houssami receives research support through a National Breast Cancer Foundation (Australia), Breast Cancer Research Leadership Fellowship.

Author information

Authors

Corresponding author

Correspondence to Nehmat Houssami.

Ethics declarations

Competing interests

The authors declare that they have no competing financial interests.

Rights and permissions

Reprints and Permissions

Houssami, N., Hunter, K. The epidemiology, radiology and biological characteristics of interval breast cancers in population mammography screening. npj Breast Cancer 3, 12 (2017). https://doi.org/10.1038/s41523-017-0014-x

• Revised:

• Accepted:

• Published:

• DOI: https://doi.org/10.1038/s41523-017-0014-x

• Differential detection by breast density for digital breast tomosynthesis versus digital mammography population screening: a systematic review and meta-analysis

• Tong Li
• Nehmat Houssami
• M. Luke Marinovich

British Journal of Cancer (2022)

• Screen-detected and interval breast cancer after concordant and discordant interpretations in a population based screening program using independent double reading

• Marit A. Martiniussen
• Solveig Hofvind

• Sensitivity and specificity of screening mammography without clinical breast examination among Japanese women aged 40–49 years: analysis of data from the J-START results

• Takayoshi Uematsu

Breast Cancer (2022)

• Radiological review of prior screening mammograms of screen-detected breast cancer

• Tone Hovda
• Kaitlyn Tsuruda
• Solveig Hofvind

• Can artificial intelligence reduce the interval cancer rate in mammography screening?

• Kristina Lång
• Solveig Hofvind


text:
$$\require{cancel}$$

# 8.7: Energy-Shifts and Decay-Widths

We have examined how a state , other than the initial state , becomes populated as a result of some time-dependent perturbation applied to the system. Let us now consider how the initial state becomes depopulated.

In this case, it is convenient to gradually turn on the perturbation from zero at . Thus,

 (821)

where is small and positive, and is a constant.

In the remote past, , the system is assumed to be in the initial state . Thus, , and . Basically, we want to calculate the time evolution of the coefficient . First, however, let us check that our previous Fermi golden rule result still applies when the perturbing potential is turned on slowly, instead of very suddenly. For we have from Equations (795)-(796) that

 (822) (823)

where . It follows that, to first order, the transition probability from state to state is

 (824)

The transition rate is given by

 (825)

Consider the limit . In this limit, , but

 (826)

Thus, Equation (825) yields the standard Fermi golden rule result

 (827)

It is clear that the delta-function in the above formula actually represents a function that is highly peaked at some particular energy. The width of the peak is determined by how fast the perturbation is switched on.

Let us now calculate using Equations (795)-(797). We have

 (828) (829) (830)

Thus, to second order we have

 (831)

Let us now consider the ratio , where . Using Equation (831), we can evaluate this ratio in the limit . We obtain

This result is formally correct to second order in perturbed quantities. Note that the right-hand side of Equation (832) is independent of time. We can write

 (833)

where

 (834)

is a constant. According to a well-known result in pure mathematics,

 (835)

where , and denotes the principal part. It follows that

 (836)

It is convenient to normalize the solution of Equation (833) such that . Thus, we obtain

 (837)

According to Equation (744), the time evolution of the initial state ket is given by

 (838)

We can rewrite this result as

 (839)

It is clear that the real part of gives rise to a simple shift in energy of state , whereas the imaginary part of governs the growth or decay of this state. Thus,

 (840)

where

 (841)

and

 (842)

Note that the energy-shift is the same as that predicted by standard time-independent perturbation theory.

The probability of observing the system in state at time , given that it is definately in state at time , is given by

 (843)

where

 (844)

Here, use has been made of Equation (817). Clearly, the rate of decay of the initial state is a simple function of the transition rates to the other states. Note that the system conserves probability up to second order in perturbed quantities, because

 (845)

The quantity is called the decay-width of state . It is closely related to the mean lifetime of this state,

 (846)

where

 (847)

According to Equation (839), the amplitude of state both oscillates and decays as time progresses. Clearly, state is not a stationary state in the presence of the time-dependent perturbation. However, we can still represent it as a superposition of stationary states (whose amplitudes simply oscillate in time). Thus,

 (848)

where is the weight of the stationary state with energy in the superposition. The Fourier inversion theorem yields

 (849)

In the absence of the perturbation, is basically a delta-function centered on the unperturbed energy of state . In other words, state is a stationary state whose energy is completely determined. In the presence of the perturbation, the energy of state is shifted by . The fact that the state is no longer stationary (i.e., it decays in time) implies that its energy cannot be exactly determined. Indeed, the energy of the state is smeared over some region of width (in energy) centered around the shifted energy . The faster the decay of the state (i.e., the larger ), the more its energy is spread out. This effect is clearly a manifestation of the energy-time uncertainty relation . One consequence of this effect is the existence of a natural width of spectral lines associated with the decay of some excited state to the ground state (or any other lower energy state). The uncertainty in energy of the excited state, due to its propensity to decay, gives rise to a slight smearing (in wavelength) of the spectral line associated with the transition. Strong lines, which correspond to fast transitions, are smeared out more that weak lines. For this reason, spectroscopists generally favor forbidden lines (see Section 8.10) for Doppler-shift measurements. Such lines are not as bright as those corresponding to allowed transitions, but they are a lot sharper.

format: plain


text:
ISSN 1000-1239 CN 11-1777/TP

• 人工智能 •

### 粒向量与K近邻粒分类器

1. (厦门理工学院计算机与信息工程学院 福建厦门 361024) (cym0620@163.com)
• 出版日期: 2019-12-01
• 基金资助:
国家自然科学基金项目(61573297,61976183)；福建省出国留学奖学基金项目；福建省自然科学基金项目(2016J01198,2019J01850)；福建省教育厅A类项目(JA15363)；厦门市科技计划指导项目(3502Z20179038)

### Granular Vectors and K Nearest Neighbor Granular Classifiers

Chen Yuming, Li Wei

1. (College of Computer and Information Engineering, Xiamen University of Technology, Xiamen, Fujian 361024)
• Online: 2019-12-01

Abstract: K nearest neighbor (KNN) classifier is a classical, simple and effective classifier. It has been widely employed in the fields of artificial intelligence and machine learning. Aiming at the problem that traditional classifiers are difficult to deal with uncertain data, we study a technique of neighborhood granulation of samples on each atom feature, construct some granular vectors, and propose a K nearest neighbor classification method based on these granular vectors in this paper. The method introduces a neighborhood rough set model to granulate samples in a classification system, and the raw data can be converted into some feature neighborhood granules. Then, a granular vector is induced by a set of neighborhood granules, and several operators of granular vectors are defined. We present two metrics of granular vectors which are relative granular distance and absolute granular distance, respectively. The monotonicity of distance of granular vectors is proved. Furthermore, the concept of K nearest neighbor granular vector is defined based on the distance of granular vectors, and K nearest neighbor granular classifier is designed. Finally, the K nearest neighbor granular classifier is compared with the classical K nearest neighbor classifier using several UCI datasets. Theoretical analysis and experimental results show that the K nearest neighbor granular classifier has better classification performance under suitable granulation parameters and k values.


text:
# A differential equation

Think of $t$ and $r$ as two independent variables.

• Suppose $E$ be a function of $r$ and $V~$ be a function of $(t,r)$ such that both go to $0$ at $r=0$.

• There exists a positive function $M(r)$ such that $M(0)=0$ and $V(t,r) = -\dfrac{M(r)}{R(t,r)}$ where $R$ is another positive function such that $R(0,r)=r$.

• Let $p(r) = \dfrac{E(r)}{V(0,r)}$ be a function regular at $r=0$ such that $p(0) \in (-\infty,1)$.

• Also define a function $a$ of $r$ such that, $a(r) = \dfrac{M(r)}{\dfrac{4}{3}\pi r^3}$. Then $a$ is also a positive definite function with a well-defined value at $r=0$.

• Define $\alpha = a(0)$

Now look at this differential equation,

$$\frac{\dot{R}^2}{2} + V(t,r) = E(r)$$

Apparently this differential equation has a solution of the form,

$$\frac{t}{t_0} = \sqrt{\frac{\alpha}{a(r)}}\frac{F(p(r))}{F(p(0))} \left [1 - \left ( \dfrac{R(t,r)}{r} \right)^{\dfrac{3}{2}}~\cdot~\dfrac{F\left(~~ \dfrac{p(r)R(t,r)}{r} \right) }{F(p(r))} \right ]$$

where $t_0 = \sqrt {\dfrac{3}{8\pi \alpha}} F(p(0))$

and the function $F$ is defined over the interval $(-\infty,1)$ as,

$$F(x) = \left\{ \begin{array}{c c} -\frac{\sqrt{1-x}}{x} - \frac{1}{(-x)^{\frac{3}{2}}} \tanh^{-1} \left [ \sqrt{\frac{x}{x-1}} \right ] & x<0 \\ \frac{2}{3} & x =0 \\ \frac{1}{x^{\frac{3}{2}}}tan^{-1} \left [ \sqrt{\frac{x}{1-x}} \right ] - \frac{\sqrt{1-x}}{x} & 0<x<1 \end {array} \right.$$

How does one get the above solution?

-
What do you mean by a "positive definite function"? And how does that reconcile with the notion that $M(0) = 0$? – Willie Wong Oct 11 '10 at 22:45
@Willie Thanks for pointing out the typo. I have corrected it. Any help with solving this differential equation? – Anirbit Oct 13 '10 at 6:26
I've fixed your latex: the problem was that you needed to \-escape a \{ and all \\, and that the < sign has to be written in some cases using an HTML escape (for silly reasons! Of course, in comments the rules are different...) – Mariano Suárez-Alvarez Oct 13 '10 at 20:26
What is $\dot{R}$, is it $\partial R/\partial t$? Also, there seems to be a lot of interdependence among the definitions; can you tell us what is given for a particular instance of the problem, and what is to be determined? Better yet, if you could provide the original source or motivation for this problem, it might make things clearer. – Rahul Oct 13 '10 at 20:45
@Mariano Thanks for correcting the LaTeXing. @Rahul Yes $\dot{R}$ is partial derivative of $R$ with respect to it. I didn't understand the second part of your query. I think I have completely defined all the quantities in question. You see any ambiguities? This is taken from a paper and I am giving you the reference if that helps, "Strength of naked singularities in Tolman-Bondi spacetimes" by R.P.A.C Newman in Class. Quantum Grav.3 (1986) 527-539 The third page of the paper has this. Will be happy to get back any help. – Anirbit Oct 14 '10 at 4:33

I'm sort of just guessing here (partly based on the solution already found). By explicitly plugging in $V(t,r) = - \frac{M(r)}{R(t,r)}$, you arrive at the ordinary differential equation (for each fixed $r$) for $R$ as

$$\dot{R}^2 - \frac{2M}{R} = 2 E$$

where $M$ and $E$ are constants in time. Now, re-scale the original equation by $t = \lambda s$ and $R = \mu \rho$. Then $\partial_t R = \frac{\mu}{\lambda} \partial_s \rho$. Then you can solve $(\frac{\mu}{\lambda})^2 = \frac{2M}{\mu} = 2E$ to reduce the equation to

$$\dot{\rho}^2 - \frac{1}{\rho} = 1$$

(the weights $\mu$ and $\lambda$ will, roughly speaking, give you the weights $p(r)$ and $a(r)$ in your question). Now note that this scaling degenerates if $E = 0$. In the case that $E = 0$, the equation can be solved by quadrature:

$$\dot{x}^2 = x^{-1} \Rightarrow \sqrt{x} dx = dt \Rightarrow x^{3/2} \sim t$$

This gives the solution to the homogeneous case. In the inhomogeneous case, you take that as a sort of integrating factor: assume that $\rho^{3/2} f(\rho) \sim t$, this implies that

$$\dot{\rho} \left( \rho^{3/2} f(\rho) \right)' = 1$$

we plug this into the equation, which we first re-arrange as

$$\dot{\rho} = \sqrt{\frac{1}{\frac{\rho}{1+\rho}}}$$

and we conclude that

$$\sqrt{\frac{\rho}{1+\rho}} = \frac{d}{d\rho}( \rho^{3/2} f(\rho))$$

and you solve this by directly integrating it. I think this $f$ you find should be exactly the $F$ you wrote down above (I didn't check it myself). Note that due to the singular weight $\rho$ which degenerates as $\rho \to 0$, you will have to separately integrate in the regime where $\rho > 0$ and $\rho < 0$. The existence and uniqueness of solution is guaranteed by the theory of Fuchsian ODEs.

-
Thanks a lot for this help. Are you defining $f$ as, $f(\rho) = \frac{kt}{\rho ^ \frac{3}{2}}$ ? (for some constant $k$) Since there are no other replies I am giving away the bounty to you. (Though I am yet to understand your solution completely) – Anirbit Oct 19 '10 at 6:18
Actually I think I defined it with $k = 1$. The constant $k$ can be absorbed into the (implicit) definition of $\rho$, by rescaling $\rho$; so it is not too important. The reason I wrote $\sim t$ instead of $=t$ is just because there can be a constant term: $f(\rho) = (kt + C) / \rho^{3/2}$. who doesn't change the derivative. (In fact, I think in the final answer, to match the boundary conditions there may need to be a $C$.) – Willie Wong Oct 19 '10 at 10:06


text:
# code for bipartite graphs

How to write a code for obtaining a bipartite graph where the edges are indexed by some numbers?e.g if i write the code as D = DiGraph({ 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] }) then only graph is coming but the edges are not indexed here.How should i modify this so that edges of the graph will be indexed?

edit retag close merge delete

Sort by » oldest newest most voted

Instead of a dictionary, do a dictionary of dictionaries specifying the labels of the edges. In your example:

sage: D = DiGraph({ 0: {1:123 , 2:234 , 3:12}, 1: {0:'a string', 2:42}, 2: {3:0}, 3: {4:34}, 4: {0:40, 5:11}, 5: {1:123} })

Note that you can label edges by strings as well if you want.

When plotting, if you want to see the labels, you should do:

sage: D.plot(edge_labels=True)

more

but in your code the labels are merged on the edges.can i do so that labels will show above the edges without merging on them?

( 2013-03-28 14:03:38 +0200 )edit

You mean the labels and edges in the plot? Or what do you mean by merge?

( 2013-03-28 14:24:06 +0200 )edit

yeah because it is difficult to read the labels from the edges.so is there any code so that labels will be clear?

( 2013-03-28 14:27:52 +0200 )edit

It's not completely clear to me what you mean by "indexing" a graph edge. If you want to give them labels, you can do that using set_edge_label:

sage: D = DiGraph({ 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] })
sage: D.edges()
[(0, 1, None),
(0, 2, None),
(0, 3, None),
(1, 0, None),
(1, 2, None),
(2, 3, None),
(3, 4, None),
(4, 0, None),
(4, 5, None),
(5, 1, None)]
sage: for i, (u, v, l) in enumerate(D.edges()):
....:     D.set_edge_label(u, v, "edge # {}".format(i))
....:
sage: D.edges()
[(0, 1, 'edge # 0'),
(0, 2, 'edge # 1'),
(0, 3, 'edge # 2'),
(1, 0, 'edge # 3'),
(1, 2, 'edge # 4'),
(2, 3, 'edge # 5'),
(3, 4, 'edge # 6'),
(4, 0, 'edge # 7'),
(4, 5, 'edge # 8'),
(5, 1, 'edge # 9')]
sage: D.show(edge_labels=True)

produces

more


text:
Select Page

# Equations and graphs

Consider this table of values of $x$ and $y$.

 $x$ $y$ 0 20 1 30 2 40 3 50

Notice that for every increase of $1$ in the $x$ the $y$ increases by $10$. This constant difference shows that there is a linear relationship between $x$ and $y$.  If we plot the values on the axes we get the straight line in the graph above.

The gradient of the line is $10$. The gradient of any line can be calculated using the formula rise over run (either by reading off the graph or using any two coordinates from the table).

$gradient = m =$ $\frac{rise}{run}$ $=$ $\frac{y_2 - y_1}{ x_2 - x_1}$

e.g.     Point 1: $(x_1,y_1) =$  $(1,30)$ and Point 2: $(x_1,y_1) =$ $(3,50)$

$gradient = m =$  $\frac{50 - 30}{3 - 1}$ $=$ $\frac{20}{ 2}$ $= 10$

## Straight line equations

The general form of a straight line is   $y = mx + c$

Where $m$ is the gradient of the line and $c$ is the $y$ intercept (i.e. where the line crosses the $y$ axis).
This form is handy for sketching a line and for reading off the gradient.

e.g. Sketch the line   $y = -\frac{1}{2}x + 10$

The $gradient =$ $-\frac{1}{2}$ and the $y$ $intercept = 10$

Note that sometimes we need to rearrange an equation into the form $y = mx + c$.

e.g.  Find the gradient and y intercept of the line $2y - 6x = 4$

 $2y = 4 + 6x$
 $y = 2 + 3x$

The line will cut the $y$ axis at $2$ with a gradient of $3$.

Use the desmos online calculator to draw different straight lines to understand the relationship between the equation and the graph.

### Horizontal lines

Line: $y= 7$

### Vertical Lines

Line: $x=6$

### Parallel Lines

Lines: $y=x+4$ and $y=x+1$

The gradient of parallel lines are equal.

## Tables and graphs drag and drop activity

Complete the following interactive activity

## Further information

• Press the Printer Friendly button at the top left-hand corner to download a printable handout
• Khan academy uses video to explain another worked example of drawing a line with slope and intercept and a set of  practice problems that you can use to review your understanding.


text:
# Among the following ethers, which one will produce methyl alcohol on treatment with hot concentrated HI?

Updated On: 17-04-2022

Get Answer to any question, just click a photo and upload the photo
and get the answer completely free,

Text Solution

CH_(3)-CH_(2)-underset(CH_(3))underset(|)(CH)-O-CH_(3)CH_(3)-underset(CH_(3))underset(|)overset(CH_(3))overset(|)(C)-O-CH_(3)CH_(3)-underset(CH_(3))underset(|)(CH)-CH_(2)-O-CH_(3)CH_(3)-CH_(2)-CH_(2)-CH_(2)-O-CH_(3)

B

Step by step solution by experts to help you in doubt clearance & scoring excellent marks in exams.

Transcript

hello everyone latest all the spatial the questions that among the following ethers which one will produce methyl alcohol on treatment with hot concentrated at this question as you can see here given four options in the four options we have each other then they have to tell that in which of the following Each Other they will be production of methyl alcohol when it will be treated with hot concentrated Aish hot concentrated extract letters in the first option when it will be reacted with HIV in HIV there will be a negative so they will be nucleophilic substitution and hear the reaction proceeds through SN2 mechanism this I negative will attack that carbon which will be less sterically hindered if you see this oxygen this carbon will be less sterically hindered the hair on Oxygen they will be partial negative charge and on Carbon there will be partially

because of the chain is electronegative nucleophile and negative will attack this carbon and when this bond will break like this so as you know in SN2 mechanism the reaction occurs in only single step both the processes will occur in the single step hair the product which we get will be CH3 ch2 ch2 CH3 and here we get because when O negative will be formed then it will attack the hydrogen which is present in Exide since I neglected nucleophile attack this carbon source from here we get CH3 I write this is the product in second reaction when they will be reaction with H I so we have a Negative Ion which factors and nucleophile now

the difference because as you can see adjacent to the oxygen we have this carbon and this Karbonn when they will be positive charge in this Karbonn we get a tertiary Carbon ke time which is very stable a very much stable according to SN1 mechanism will proceed by SN1 mechanism which occurs in two step so hair first of all there will be formation of ka book a time when this bond will break there will be formation of Carbon ke time and hair Karbonn will carry a positive charge then this I negative will attack this carbon from here the product will be ch3cl ch3br ch3i plus CH3 CH3 O negative then it will attack the hydrogen

now in third option when it will react with H I will again here SN2 mechanism will be there so here I negative nucleophile will attack the carbon which will be less study conducted right so hair it will attack this carbon atom which will be partial positive and here Oxygen will be partially negative when it will take this Karbonn this god will break so the product will be CH3 ch2 CH3 ch2 CH3 I product latest see the fourth reaction to import option when it will react with H I again here SN2 mechanism will be there for nucleophilic substitution

baby partial negative and oxygen partial positive and carbon so this nucleophile and negative attack this carbon in this bond will break like this the from here we get CH3 ch2 ch2 ch2 + ch3i these are the product of the reaction in which we are getting methyl alcohol it is S reaction we have ch3oh found in this reaction which methyl alcohol methyl alcohol methyl alcohol based on their Sudha correct option will be option to answer is option to thank you


text:
# Multiplicative Interactions and Where to Find Them

Anonymous

We explore the role of multiplicative interaction as a unifying framework to describe a range of classical and modern neural network architectural motifs, such as gating, attention layers, hypernetworks, and dynamic convolutions amongst others. Multiplicative interaction layers as primitive operations have a long-established presence in the literature, though this often not emphasized and thus under-appreciated... (read more)

PDF Abstract


text:
# How do you factor completely ax – ay + x^2 – xy?

Apr 29, 2016

$\text{ } \left(x - y\right) \left(a + x\right)$

#### Explanation:

These are not always easy to spot!

Group as:$\text{ } \left(a x - a y\right) + \left({x}^{2} - x y\right)$

Factoring out common values from each bracket

$\text{ } a \left(x - y\right) + x \left(x - y\right)$

Again factor out but this time factor out $\left(x - y\right)$

$\text{ } \left(x - y\right) \left(a + x\right)$


text:
# Simplifying Activity-on-Edge Graphs

We formalize the simplification of activity-on-edge graphs used for visualizing project schedules, where the vertices of the graphs represent project milestones, and the edges represent either tasks of the project or timing constraints between milestones. In this framework, a timeline of the project can be constructed as a leveled drawing of the graph, where the levels of the vertices represent the time at which each milestone is scheduled to happen. We focus on the following problem: given an activity-on-edge graph representing a project, find an equivalent activity-on-edge graph (one with the same critical paths) that has the minimum possible number of milestone vertices among all equivalent activity-on-edge graphs. We provide a polynomial-time algorithm for solving this graph minimization problem.

## Authors

• 54 publications
• 5 publications
• 3 publications
10/05/2017

### Complexity of Edge Monitoring on Some Graph Classes

In this paper, we study the complexity of the edge monitoring problem. A...
02/10/2018

### Searching isomorphic graphs

To determine that two given undirected graphs are isomorphic, we constru...
12/04/2021

### Quasiplanar graphs, string graphs, and the Erdos-Gallai problem

An r-quasiplanar graph is a graph drawn in the plane with no r pairwise ...
06/30/2019

### Connecting edge-colouring

This paper studies the problem of connecting edge-colouring. Given an un...
03/23/2020

### A Toroidal Maxwell-Cremona-Delaunay Correspondence

We consider three classes of geodesic embeddings of graphs on Euclidean ...
12/10/2020

### Path Optimization Sheaves

Motivated by efforts to incorporate sheaves into networking, we seek to ...
12/24/2018

### Cops, robbers, and burning bridges

We consider a variant of Cops and Robbers wherein each edge traversed by...
##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1 Introduction

The critical path method is used in project modeling to describe the tasks of a project, along with the dependencies among the tasks; it was originally developed as PERT by the United States Navy in the 1950s [malcolm1959application]. A dependency graph is used to identify bottlenecks, and in particular to find the longest path among a sequence of tasks, where each task has a required length of time to complete (this is known as the critical path).

In this paper we are interested in the problem of visualizing an abstract timeline of the possible critical paths of a given project, represented abstractly as a partially ordered set of tasks, at a point in the project planning at which we do not yet know the time lengths of each task. The most common method of visualizing partially ordered sets, as an activity-on-node graph (a transitively reduced directed acyclic graph with a vertex for each task) is unsuitable for this aim, because it represents each task as a point instead of an object that can extend over a span of time in a timeline. To resolve this issue, we choose to represent each task as an edge in a directed acyclic graph. In this framework, the endpoints of the task edges have a natural interpretation, as the milestones of the project to be scheduled. Additional unlabeled edges do not represent tasks to be performed within the project, but constrain certain pairs of milestones to occur in a certain chronological order. The resulting activity-on-edge graph can then be drawn in standard upward graph drawing style [bt1992area, battista1998graph, gt2001computational, gt1995upward, ahr2010improving]. Alternatively, once the lengths of the tasks are known and the project has been scheduled, this graph can be drawn in leveled style [junger1999level, hkl2004characterization], where the level of each milestone vertex represents the time at which it is scheduled.

It is straightforward to expand an activity-on-node graph into an activity-on-edge graph by expanding each task vertex of the activity-on-node graph into a pair of milestone vertices connected by a task edge, with the starting milestone of each task retaining all of the incoming unlabeled edges of the activity-on-node graph and the ending milestone retaining all of the outgoing edges. It is convenient to add two more milestones at the start and end of the project, connected respectively to all milestones with no incoming edges and from all milestones with no outgoing edges. The size of the resulting activity-on-edge graph is linear in the size of the activity-on-node graph. An example of such a transformation is depicted in Figure 1.

However, the graphs that result from this naive expansion are not minimal. Often, one can merge some pairs of milestones (for instance the ending milestone of one task and the starting milestone of another task) to produce a simpler activity-on-edge graph (such as the one for the same schedule in Figure 2). Despite having fewer milestones, this simpler graph can be equivalent to the original, in the sense that its critical paths (maximal sequences of tasks that belong to a single path in the graph) are the same. By being simpler, this merged graph should aid in the visualization of project schedules. In this paper we formulate and provide a polynomial time algorithm for the problem of optimal simplification of activity-on-edge graphs.

### 1.1 New Results

We describe a polynomial-time algorithm which, given an activity-on-edge graph (i.e., a directed acyclic graph with a subset of its edges labeled as tasks), produces a directed acyclic graph that preserves the critical paths of the graph and has the minimum possible number of vertices among all critical-path-preserving graphs for the given input. Our algorithm is agnostic about the weights of the tasks. In more general terms, the resulting graph has the following properties:

• The task edges in the given graph correspond one-to-one with the task edges in the new graph.

• The new graph has the same dependency (reachability) relation among task edges as the original graph.

• The new graph has the same potential critical paths as the original graph.

• The number of vertices of the graph is minimized among all graphs with the first three properties.

Our algorithm repeatedly applies a set of local reduction rules, each of which either merges a pair of adjacent vertices or removes an unlabeled edge, in arbitrary order. When no rule can be applied, the algorithm outputs the resulting graph.

We devote the rest of this section to related work and then describe the preliminaries in Section 2. We then present the algorithm in Section 3 and show in Section 4 that its output preserves the potential critical paths of the input, and in Section 5 that it has the minimum possible number of vertices. We also show that the output is independent of the order in which the rules are applied. We discuss the running time in Section 6 and conclude with Section 7.

### 1.2 Related work

Constructing clear and aesthetically pleasing drawings of directed acyclic graphs is an old and well-established task in graph drawing, with many publications [sugiyama1981methods, battista1998graph, bm2001layered, hn2014hierarchical]. The work in this line that is most closely relevant for our work involves upward drawings of unweighted directed acyclic graphs [bt1992area, gt2001computational, gt1995upward, ahr2010improving] or leveled drawings of directed acyclic graphs that have been given a level assignment [junger1999level, hkl2004characterization] (an assignment of a -coordinate to each vertex, for instance representing its height on a timeline).

Although multiple prior publications use activity-on-edge graphs [kulkarni1984compact, cg1986parallel, arh1994nearcritical, hd2011project] and even consider graph drawing methods specialized for these graphs [xu2010automatic], we have been unable to locate prior work on their simplification. This problem is related to a standard computational problem, the construction of the transitive reduction of a directed acyclic graph or equivalently the covering graph of a partially ordered set [agu1972transitive]. We note in addition our prior work on augmenting partially ordered sets with additional elements (preserving the partial order on the given elements) in order to draw the augmented partial order as an upward planar graph with a minimum number of added vertices [es2013confluent].

The PERT method may additionally involve the notion of “float”, in which a given task may be delayed some amount of time (depending on the task) without any effect on the overall time of the project [arditi2006selecting, householder1990owns]. We do not consider constraints of this form in the present work, although the unlabeled edges of our output can in some sense be seen as serving a similar purpose.

## 2 Preliminaries

We first define an activity-on-edge graph. The graph can be a multigraph to allow tasks that can be completed in parallel to share both a start and end milestone when possible.

Define an activity-on-edge graph (AOE) as a directed acyclic multigraph , where a subset of the edges of , denoted , are labeled as task edges. The labels, denoting tasks, are distinct, and we identify each edge in with its label.

Given an AOE with tasks , for all , let be the start vertex of , and let be the end vertex of .

When the considered graph is clear from context, we omit the subscript and write and . It may be that , or , or with .

To define potential critical paths formally, we introduce the following notation. Given an AOE with tasks , for all , with , say that has a path to in if there exists a path from to , or if , and write .

Given an AOE with tasks , define a potential critical path as a sequence of tasks , where for all , , and where is not a subsequence of any other sequence with this property.

Our algorithm will apply a set of transformation rules to an input AOE of a canonical form. A canonical AOE is an AOE which is naively expanded from an activity-on-node graph.

Every AOE can be transformed into a canonical AOE with the same reachability relation on its tasks. First, we start by computing the reachability relation of the tasks. The transitive closure of the resulting reachability matrix gives an activity-on-node graph (which is quadratic, in the worst case, in the size of the original AOE). Then, this activity-on-node graph can be converted to a canonical AOE as described in Section 1.

Two AOE graphs and are equivalent, i.e. , if and have the same set of tasks—i.e., there is a label-preserving bijection between the task edges of and those of —and, with respect to this bijection, and have the same set of potential critical paths.

An AOE is optimal if minimizes the number of vertices for its equivalence class: i.e., if for every AOE , .

We now formally define our problem.
Problem 1. Given a canonical AOE , find some optimal AOE with .

## 3 Simplification Rules

Our algorithm takes a canonical AOE and greedily applies a set of rules until no more rules can be applied. Given an AOE and given two distinct vertices , the simplification rules used by our algorithm are:

1. if and have no outgoing task edges and have precisely the same outgoing neighbors, merge and . Symmetrically, if and have no incoming task edges and have precisely the same incoming neighbors, merge and .

2. If has an unlabeled edge to , and has another path to , remove the edge .

3. If has an unlabeled edge to and the following conditions are satisfied, merge and :

• rule 2 is not applicable to the edge .

• if has an outgoing task, then has no incoming edge other than .

• if has an incoming task, then has no outgoing edge other than .

• every incoming neighbor of has a path to every outgoing neighbor of .

Figure 3 depicts an AOE graph and the graph output by the algorithm after applying all possible rules.

It will be convenient for the proofs in Section 5 to give a name to the output of the algorithm: An output AOE, denoted , is any AOE obtained from a canonical AOE by a sequence of applications of rules 1, 2, and 3, to which none of these rules can still be applied.

## 4 Correctness

In this section we prove the correctness of our algorithm (its output graph is equivalent to its input graph).

We begin with preserving potential critical paths. We show that the rules never change the existence or nonexistence of a path from one task to another, and that this implies preservation of potential critical paths.

Given two AOEs and with the same set of tasks , and have the same reachability relation on the tasks if and only if .

###### Proof.

Trivially, we have (or ) if and only if is earlier than in some potential critical path of (or ). Therefore, preservation of critical paths is equivalent to preservation of the reachability relation. ∎

The output of the algorithm is equivalent to its input.

###### Proof.

We show the invariant that given tasks and , at a given iteration of the algorithm if and only if at the next iteration. From this it follows that the output of the algorithm has the same reachability relation on its tasks as the input, and then the lemma follows from Lemma 4.

The invariant is true because merging a pair of vertices (rules 1 and 3) never disconnects a path, and no edge is ever removed (by rule 2) between two vertices unless another path exists between the two vertices. In particular, the end vertex of still has a path to the start vertex of after the application of any of the rules.

For the other direction, removing an edge never introduces a new path. Furthermore, if vertices and are merged by applying rule 1, and if some vertex has a path to some vertex through the newly merged , then the condition of rule 1 ensures that has a path, through or , to before the merge. Similarly, suppose and are merged by applying rule 3. Then if has a path to through , then (abusing notation) either and before the merge, so (via the edge ), or for some incoming neighbor of and outgoing neighbor of , and . In this case, by the conditions of the rule, before the merge. ∎

[] Any intermediate graph that results from applying rules of the algorithm to an input canonical AOE graph, is acyclic.

###### Proof.

Given Section 2 and Section 2, the canonical AOE input is acyclic. Now we show none of the rules can create a cycle after being applied to an intermediate acyclic graph . This is obvious for rule 2 as it removes edges. Suppose for a contradiction that merging vertices and creates a cycle. The cycle must involve the new vertex resulting from the merge. For rule 1, this implies the existence of a cycle in either from or to itself which is a contradiction. For rule 3, it implies the existence of a cycle in including the unlabeled edge or a cycle including an incoming neighbor of and an outgoing neighbor of , which is a contradiction. ∎

Any graph output by the algorithm is acyclic.

## 5 Optimality

In this section we prove the optimality of our algorithm: it uses as few vertices as possible. Let be any output AOE. Let Opt be any optimal AOE such that . Our proof relies on an injective mapping from the vertices of to the vertices of Opt. The existence of this mapping shows that has at most as many vertices as Opt, and therefore has the optimal number of vertices. Once we have identified the vertices of with the vertices of Opt in this way, we show that, for a given input, any two graphs output by the algorithm (but not necessarily Opt) must have the same unlabeled edges. Since the task edges are determined, and since the injective mapping to Opt determines the vertices, determining the unlabeled edges implies the order-independence of our algorithm’s choice of simplification rules.

Before defining the mapping between and Opt, we establish some facts about the structure of .

For every unlabeled edge in any output AOE , there exist tasks and such that and .

###### Proof.

By Definition 3, is produced by the algorithm from some canonical AOE . This property holds for by Section 2. As every rule of the algorithm either removes an unlabeled edge or merges two vertices, and never creates a new edge or vertex, the proof is complete. ∎

Every vertex in an output AOE has an incident task edge.

We can now define a mapping from the vertices of to those of Opt:

Given an output AOE with task set , and given an optimal AOE Opt with , let be the following mapping: for every :

• Let , for some for which , if such a task exists.

• Let , where , otherwise.

As shown in Section 5, every vertex in has an incident task edge, and by Definition 2, and Opt have the same set of tasks. Therefore, this mapping is well-defined (up to its arbitrary choices of which task to use for each ). To prove that is injective, we will use the fact that since , and Opt have the same reachability relation (by Section 4 and Section 4).

The heart of the proof that is injective lies in showing that if two tasks do not share a vertex in , the corresponding tasks also do not share the corresponding vertices in Opt. From this it follows that cannot map distinct vertices in to the same vertex in Opt.

Given an output AOE , and an optimal AOE , with task set , let and be two distinct tasks in . If , then . If , then .

###### Proof.

Suppose for a contradiction that , but (the other case is symmetrical). Let and . Consider the following (exhaustive) cases for and :

1. and have no incoming edges

2. or has an incoming unlabeled edge, but neither nor has an incoming task edge

3. or has an incoming task edge

In case 1, applying rule 1 results in merging and . However, since is the output of the algorithm, no rule can be applied to . This is a contradiction.

In case 2, and cannot have the same incoming neighbors or else rule 1 would apply. We may assume without loss of generality that there exist a vertex and an unlabeled edge , such that the edge does not exist. By Section 5, there exists a task where . Since and (by Lemma 4), then by Lemma 4, , so , since . Again by Lemma 4, , so there is a path from to . If , then this contradicts that does not exist. Suppose . Then we show there exist some vertex and an unlabeled edge . The following cases are exhaustive:

1. contains a path from to . As such a path to exists and has no incoming task edge, there exist a vertex and an unlabeled edge (), not belonging to unless rule 3 can be applied to vertex and its incoming neighbor in path .

2. does not contain a path from to . As , an unlabeled edge belonging to path exists.

Given the existence of , by Section 5, there exists a task where . , so by reasoning similar to the above, . Then, one can apply rule 2 and either remove edge in case a or in case b (Figure 5); this contradicts the definition of .

In case 3, we can assume without loss of generality that has an incoming task ; consequently, . Then, by Lemma 4, we have and thus via a path . Consider the following cases for :

2. is a sequence of unlabeled edges

In case a, by Lemma 4 , and thus , and therefore . This creates a cycle between and , contradicting Section 4.

In case b, illustrated in  Figure 5, since rule 3 cannot be applied (if it could, this would contradict the definition of ), there exist a vertex not on the path from to , and an edge (a task edge or an unlabeled edge). Therefore, there exists a task where either or by Section 5, . Considering Opt and applying Section 4, so . This path either creates a cycle in or allows for removing edge by rule 2, which is a contradiction.

Thus if , then .

[]

Given an output AOE , and an optimal AOE , with task set , let and be two distinct tasks in . If , then .

###### Proof.

The proof, which is in Appendix A.1, uses essentially the same approach as the proof of Lemma 5: supposing that the two vertices are the same, then using the fact that and Opt have the same reachability relation on their tasks, and the definition of as having no more rules to apply, to derive a contradiction.

There is one remaining technicality: we have defined an optimal AOE as being acyclic; the question arises whether one could reduce the number of vertices by allowing (unlabeled) cycles. However, this is not the case; it is easy to see that any unlabeled cycle can be merged into one vertex, reducing the number of vertices, without changing the reachability relation on the tasks.

We are ready to prove our main results. Given a canonical AOE , the algorithm produces an optimal AOE .

###### Proof.

Let be the output AOE produced by the algorithm on . Given any optimal AOE Opt and , the mapping in Section 5 is injective: suppose for a contradiction that and are distinct vertices in , and . Then by the definition of , either , , and have the same incoming task, or , , and have the same outgoing task, or there exist tasks and such that (without loss of generality) , and . By Lemmas 5 and 5, all three of these cases imply that .

Therefore, . Furthermore, , by Lemma 4. The theorem follows. ∎

Given an input, the algorithm produces the same output regardless of the order in which the rules are applied.

###### Proof.

As stated earlier, all task edges of an input canonical AOE are present in any output of the algorithm and the mapping determines the vertices. Therefore, it suffices to show that any two graphs output by the algorithm have the same set of unlabeled edges. Suppose for a contradiction that and are two distinct outputs of the algorithm, resulting from applying different sequences of rules. By Section 5, the algorithm always produces an optimal AOE. Therefore, . Since , there is an unlabeled edge in (without loss of generality) that is not in . By Section 5, there exist task edges and such that and . We have . Since by Section 4 and Section 4, and both preserve the reachability relation of the tasks of , we have . Consider the cases for path from to in :

1. There exists a task in other than and .

2. Path is a sequence of unlabeled edges.

In case 1, we have and therefore, . Then by rule 2, one can remove the edge , which contradicts the definition of .

In case 2, the length of is at least two, and contains a vertex . By Section 5, there exist tasks and where . Now, since , both graphs are optimal, and both graphs are outputs of the algorithm, Lemma 5 implies that . Call this vertex . Then there exists a path from to , through , by Lemma 4, and one can remove the edge by rule 2. This contradicts the definition of . ∎

## 6 Analysis

Let be the number of vertices in a canonical AOE (which is linear in the number of tasks), and the number of unlabeled edges. There are at most iterations in the algorithm, because each iteration either merges two vertices or removes an edge, by applying one of the three rules. This requires finding an edge to remove ( potential edges) or two vertices to merge ( potential pairs), then performing the merge or the removal. Intuitively, our algorithm runs in polynomial time as it takes polynomial time to find and apply a rule.

We provide a faster implementation of our algorithm than the naive approach. The algorithm transforms a canonical AOE graph into an optimal AOE graph by applying rules 1, 2 or 3. For simplicity, we label the vertices . At each iteration, compute a reachability matrix for the current graph. indicates whether there exist zero, one, or more than one paths from to . In order to compute , for all and initialize if the edge exists. Then sort the vertices in topological order (such an ordering exists according to Section 4). For each vertex in this order, and for each vertex , set to , where is the set of all vertices such that either or there exists an edge . This procedure takes time. Algorithm 1 provides a summary.

Given the reachability matrix, an unlabeled edge is removed by rule 2 in time, if . Therefore, checking rule 2 for all edges takes time.

Without loss of generality, for rule 1, we only consider merges of pairs of vertices with the same outgoing neighbors. This requires, for each vertex with no outgoing task edge, a sorted list of outgoing neighbors (S). To obtain such lists for all vertices, list unlabeled edges as pairs of vertices and sort all the pairs with two bucket sorts: first over the first elements of the pairs, then over the second elements. Breaking the sorted list into chunks of pairs with the same first element (say ), gives the outgoing neighbors of , in the second elements of the pairs, in a numerically sorted order. This takes time. Then find pairs of vertices to merge, if any exist: first, bucket sort vertices based on their out-degree. Vertices in different buckets cannot be merged by rule 1. For each bucket containing vertices with degree (), call MergeDetection:

The vertices in each resulting bucket have the same outgoing neighbors and can be merged by rule 1. As each vertex with degree appears in one bucket in each of iterations, this sort takes time. Upon merging vertices and , name the new vertex min.

To check rule 3, for each vertex , compute : the intersection of the reachable sets of the incoming neighbors of . This takes time. Consider only those unlabeled edges that meet the preconditions of rule 3 concerning the existence of outgoing and incoming tasks of and respectively. Test whether the last point in rule 3 applies to edge by testing in time whether all outgoing neighbors of are in .

Computing the reachability matrix takes time, and using this matrix to check for rule 2 takes time per iteration. Checking for rule 1 or 3 takes time per iteration. Further, the outer loop in Algorithm 1 runs at most times as it either merges two vertices or returns the output. This gives a total complexity of for our algorithm.

## 7 Conclusion

Our algorithm reduces the visual complexity of an activity-on-edge graph, making it easier to understand bottlenecks in a project. The algorithm repeatedly applies simple rules and therefore can be implemented easily. However, one can measure the complexity of a graph in other ways. One question for future work is whether one can minimize the number of edges in an AOE graph in polynomial time. Another question is whether one can, in polynomial time, convert an AOE graph into a graph that (i) has the same critical paths as , and (ii) has a plane drawing with fewer edge crossings than all other graphs satisfying (i).

## Appendix A Appendix

### a.1 Proof of Section 5

See 5

###### Proof.

Suppose for a contradiction that , but . Since , then by Lemma 4, , so has a path to . Consider the following possible cases for path :

1. There exists a task in .

2. only consists of unlabeled edges. Consider the cases for any unlabeled edge in :

1. There exist incident tasks and , pointing away from and toward and , respectively.

2. There exists an incident unlabeled edge pointing away from and an incident task pointing toward .

3. There exists an incident task pointing away from and an incident unlabeled edge pointing toward .

4. There exists an incident unlabeled edge pointing away from and an incident unlabeled edge pointing toward . Vertices and have no outgoing or incoming task edges, respectively.

These cases are exhaustive as path either has a task or it is a sequence of unlabeled edges. Further, for case 2, suppose for an unlabeled edge , none of the subcases of 2a, 2b, 2c and 2d holds. Then, by rule 3, one can merge vertices and ; this contradicts the definition of .

In case 1, shown in Figure 7, we have so by Section 4, . Therefore, there is a path in Opt (through ) from to . Since , this path creates a cycle in Opt. However, Opt is an AOE graph and is therefore acyclic by Section 2.

In case 2a, shown in Figure 7, , so by Section 4, , i.e. there is a path from to . Similarly, , so there is a path from to . Since , this implies , so by Section 4, . Therefore, there is a path in from to . This path creates a cycle in and contradicts Section 4.

In case 2b, shown in Figure 9, by Section 5, there exists a task where . Since we have and and , by Section 4, we have . Therefore, there is a path in from to . This path either creates a cycle between and , contradicting Section 4 or by rule 2, one can remove edge , which is a contradiction by the definition of .

Case 2c is almost identical to case 2b, and again leads to the existence of a path from to (similarly defined), resulting in either a cycle or an application of rule 2 .

In case 2d, shown in Figure 9, by Section 5, there exist task edges and where and , and unlabeled edges and . We have , then by Section 4, . Therefore, there is a path in from to . This path either creates a cycle between and , contradicting Section 4 or by rule 3, one can merge and in , which is a contradiction by the definition of .

Thus if , then .