## Abstract

We show how the value of various parameters of graphs connected to sparse matrix factorization and other applications can be approximated using an algorithm of Leighton et al. that finds vertex separators of graphs. The approximate values of the parameters, which include minimum front size, treewidth, pathwidth, and minimum elimination tree height, are no more than O(log n) (minimum front size and treewidth) and O(log^{2} n) (pathwidth and minimum elimination tree height) times the optimal values. In addition we examine the existence of bounded approximation algorithms for the parameters, and show that unless P = NP, there are no absolute approximation algorithms for them.

Original language | English |
---|---|

Title of host publication | Graph-Theoretic Concepts in Computer Science - 17th International Workshop, WG 1991, Proceedings |

Editors | Gunther Schmidt, Rudolf Berghammer |

Publisher | Springer Verlag |

Pages | 1-12 |

Number of pages | 12 |

ISBN (Print) | 9783540551218 |

DOIs | |

Publication status | Published - 1992 |

Event | 17th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1991 - Fischbachau, Germany Duration: 17 Jun 1991 → 19 Jun 1991 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 570 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 17th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1991 |
---|---|

Country/Territory | Germany |

City | Fischbachau |

Period | 17/06/91 → 19/06/91 |

### Bibliographical note

Funding Information:The notion of treewidth has several other applications (see e.g. \[Am85\]).I t is closely related to the pathwidth, which has among others important applications in the theory of VLSI layout. The pathwidth is equivalent to several other parameters of graphs, including the minimum chromatic number of an interval graph containing the graph as a subgraph and the node search number of a *Department of Computer Science, Utrecht University,P .O. Box 80.089, 3508 TB Utrecht, The Netherlands. The research of this author is partially supported by the ESPRIT II Basic Research Actions of the EC under Contract No. 3075 (project ALCOM). ?Xerox Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, California 94304 USA, and Universityo f Bergen, Norway. ?Department of Computer Science, Universityo f Iceland, 101 Reykjav(k, Iceland. Department of Computer Science, Utrecht University.T he research of this author is supported by the Foundation for Computer Science (S.I.O.N.) of the Netherlands Organization for Scientific Research (N.W.O.) and by the ESPRIT II Basic Research Actions of the EC under Contract No. 3075 (project ALCOM).

Publisher Copyright:

© Springer-Verlag Berlin Heidelberg 1992.