Sökning: "graph decomposition"

Visar resultat 1 - 5 av 29 avhandlingar innehållade orden graph decomposition.

1. 1. Graph Decomposition Using Node Labels

   Författare :Öjvind Johansson; KTH; []
   Nyckelord :graph decomposition; modular decomposition; cographs; NLC-width; clique-width;

   Sammanfattning : .... LÄS MER

3. 2. Advances in Functional Decomposition: Theory and Applications

   Författare :Andrés Martinelli; Elena Dubrova; Jon Muzio; KTH; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; computer science; electronic system design; Boolean decomposition; binary decision diagram; logic synthesis; graph algorithm; Computer science; Datavetenskap;

   Sammanfattning : Functional decomposition aims at finding efficient representations for Boolean functions. It is used in many applications, including multi-level logic synthesis, formal verification, and testing. This dissertation presents novel heuristic algorithms for functional decomposition. LÄS MER

4. 3. Graph dominators in logic synthesis and verification

   Författare :René Krenz; KTH; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; formal verification; logic synthesis; dominators; equivalence checking; decomposition; Computer science; Datavetenskap;

   Sammanfattning : This work focuses on the usage of dominators in circuit graphs in order to reduce the complexity of synthesis and verification tasks. One of the contributions of this thesis is a new algorithm for computing multiple-vertex dominators in circuit graphs. LÄS MER

5. 4. Dominator-based Algorithms in Logic Synthesis and Verification

   Författare :René Krenz-Bååth; Johnny Öberg; Joao Marques-Silva; KTH; []
   Nyckelord :TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; graph dominators; formal verification; logic synthesis; equivalence checking; decomposition; Electrical engineering; Elektroteknik;

   Sammanfattning : Today's EDA (Electronic Design Automation) industry faces enormous challenges. Their primary cause is the tremendous increase of the complexity of modern digital designs. Graph algorithms are widely applied to solve various EDA problems. LÄS MER

7. 5. Optimal and Hereditarily Optimal Realizations of Metric Spaces

   Författare :Alice Lesser; Svante Janson; Lars-Erik Persson; Anders Johansson; Vincent Moulton; Pierre Flener; Charles Semple; Uppsala universitet; []
   Nyckelord :Applied mathematics; optimal realization; hereditarily optimal realization; tight span; phylogenetic network; Buneman graph; split decomposition; T-theory; finite metric space; topological graph theory; discrete geometry; Tillämpad matematik;

   Sammanfattning : This PhD thesis, consisting of an introduction, four papers, and some supplementary results, studies the problem of finding an optimal realization of a given finite metric space: a weighted graph which preserves the metric's distances and has minimal total edge weight. This problem is known to be NP-hard, and solutions are not necessarily unique. LÄS MER