An Improved Linear Time Algorithm for Minimal Elimination Ordering in Planar Graphs that is Parallelizable

Dahlhaus, Elias (1999) An Improved Linear Time Algorithm for Minimal Elimination Ordering in Planar Graphs that is Parallelizable.
Technical Report , 10 p.

Abstract

We present an alternative linear time algorithm that computes an ordering that produces a fill-in that is minimal with respect to the subset relation. It is simpler than an earlier algorithm of the author and is easily parallelizable. The algorithm does not rely on the computation of a breadth-first search tree.


Actions:
Download: [img] Postscript
Download (189kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: 1 (Google Scholar) |
Uncontrolled Keywords: graph algorithms parallel algorithms planar graphs
Subjects:
  • 68-XX Computer science > 68Wxx Algorithms > 68W10 Parallel algorithms

  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory

  • 68-XX Computer science > 68Qxx Theory of computing > 68Q25 Analysis of algorithms and problem complexity

    		•
    Divisions: Mathematical Institute
    Related URLs:
      Deposit Information:
      ZAIK Number: zaik1999-353
      Depositing User: Archive Admin
      Date Deposited: 02 Apr 2001 00:00
      Last Modified: 19 Dec 2011 09:46
      URI: http://e-archive.informatik.uni-koeln.de/id/eprint/353