The algorithmic use of hypertree structure and maximum neighbourhood orderings
type: Item
instance of: scholarly article
title: The algorithmic use of hypertree structure and maximum neighbourhood orderings
zbMATH Open document ID: 0893.05018
DOI: 10.1016/S0166-218X(97)00125-X
author: Andreas Brandstädt
author: Victor Chepoi
author: Feodor F. Dragan
published in: Discrete Applied Mathematics
publication date: 1998-08-02T00:00:00Z
full work available at URL: dam
review text: Graphs with a tree structure which are dual (in the sense of hypergraphs) to the ones of chordal graphs are studied. These graphs are called dually chordal. The corresponding vertex elimination orderings of dually chordal graphs are the maximum neighbourhood orderings. In this paper, a systematic treatment of the algorithmic applications of maximum neighbourhood orderings is undertaken. These orderings are useful, especially for dominating-like and distance problems.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1139432
zbMATH Keywords: graphic algorithms
zbMATH Keywords: Steiner tree
zbMATH Keywords: tree structure
zbMATH Keywords: chordal graphs
zbMATH Keywords: dually chordal graphs
zbMATH Keywords: maximum neighbourhood orderings
reviewed by: G. Gutin
MaRDI profile type: Publication
cites work: Q4773298
cites work: Q4099676
cites work: Time bounds for selection
cites work: On domination problems for permutation and other graphs
cites work: A characterisation of rigid circuit graphs
cites work: Location on Tree Networks: P-Centre and n-Dispersion Problems
cites work: Labeling algorithms for domination problems in sun-free chordal graphs
cites work: Algorithmic Aspects of Neighborhood Numbers
cites work: The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
cites work: Q4318220
cites work: Domination in quadrangle-free Helly graphs
cites work: \(r\)-dominating cliques in graphs with hypertree structure
cites work: Characterizations of strongly chordal graphs
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Q4037428
cites work: `` Strong '' NP-Completeness Results
cites work: Q3216686
cites work: Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
cites work: Topics on domination
cites work: An Algorithmic Approach to Network Location Problems. I: Thep-Centers
cites work: Treewidth. Computations and approximations
cites work: Q3313580
cites work: Dominating cliques in chordal graphs
cites work: A characterization of totally balanced hypergraphs
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: Doubly Lexical Orderings of Matrices
cites work: An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
cites work: Doubly chordal graphs, steiner trees, and connected domination
cites work: Three Partition Refinement Algorithms
cites work: A heuristic for the p-center problem in graphs
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: Doubly lexical ordering of dense 0--1 matrices
cites work: Clique Graphs of Chordal and Path Graphs
cites work: A Class of Balanced Matrices Arising from Location Problems
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: Steiner trees, connected domination and strongly chordal graphs
OpenAlex ID: W2013215731
description: scientific article; zbMATH DE number 1139432