Entry Sreedhar:1995:ICD from sigplan1990.bib

Last update: Thu Apr 12 03:37:15 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | Numbers | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Sreedhar:1995:ICD,
  author =       "Vugranam C. Sreedhar and Guang R. Gao and Yong-fong
                 Lee",
  title =        "Incremental Computation of Dominator Trees",
  journal =      j-SIGPLAN,
  volume =       "30",
  number =       "3",
  pages =        "1--12",
  month =        mar,
  year =         "1995",
  CODEN =        "SINODQ",
  ISSN =         "0362-1340 (print), 1523-2867 (print), 1558-1160 (electronic)",
  ISSN-L =       "0362-1340",
  bibdate =      "Sun Dec 14 09:17:02 MST 2003",
  bibsource =    "http://portal.acm.org/; http://www.acm.org/pubs/toc/",
  URL =          "http://www.acm.org:80/pubs/citations/proceedings/plan/202529/p1-sreedhar/",
  abstract =     "Data flow analysis based on an incremental approach
                 may require that the dominator tree be correctly
                 maintained at all times (M. Carroll and B. G. Ryder,
                 1988). Previous solutions to the problem of
                 incrementally maintaining dominator trees were
                 restricted to reducible flowgraphs (G. Ramalingam and
                 T. Reps, 1994). We present a new algorithm for
                 incrementally maintaining the dominator tree of an
                 arbitrary flowgraph, either reducible or irreducible,
                 based on a program representation called the DJ-graph
                 (Vugranam C. Sreedhar and Guang R. Gao, 1995). For the
                 case where an edge is inserted, our algorithm is also
                 faster than previous approaches (in the worst case).
                 For the deletion case, our algorithm is likely to run
                 fast on the average cases.",
  acknowledgement = ack-nhfb,
  affiliation =  "Sch. of Comput. Sci., McGill Univ., Montreal, Que.,
                 Canada",
  classification = "C1160 (Combinatorial mathematics); C6110 (Systems
                 analysis and programming); C6150C (Compilers,
                 interpreters and other processors); C6150G (Diagnostic,
                 testing, debugging and evaluating systems)",
  confdate =     "22 Jan. 1995",
  conflocation = "San Francisco, CA, USA",
  confname =     "ACM SIGPLAN workshop on Intermediate representations,
                 January 22, 1995, San Francisco, CA",
  keywords =     "algorithms; Arbitrary flowgraph; Data flow analysis;
                 Deletion case; design; DJ-graph; Dominator trees;
                 Incremental approach; Incremental computation;
                 languages; performance; Program representation;
                 reliability; theory; verification",
  subject =      "{\bf G.2.2} Mathematics of Computing, DISCRETE
                 MATHEMATICS, Graph Theory, Trees. {\bf G.4} Mathematics
                 of Computing, MATHEMATICAL SOFTWARE, Algorithm design
                 and analysis. {\bf D.2.2} Software, SOFTWARE
                 ENGINEERING, Design Tools and Techniques. {\bf D.3.3}
                 Software, PROGRAMMING LANGUAGES, Language Constructs
                 and Features, Control structures. {\bf D.2.10}
                 Software, SOFTWARE ENGINEERING, Design**,
                 Representation**.",
  thesaurus =    "Data flow analysis; Incremental compilers; Trees
                 [mathematics]",
}

Related entries