Result: The algorithmic use of hypertree structure and maximum neighbourhood orderings
Title:
The algorithmic use of hypertree structure and maximum neighbourhood orderings
Authors:
Source:
Lecture Notes in Computer Science ISBN: 9783540590712
Publisher Information:
Springer Berlin Heidelberg, 1995.
Publication Year:
1995
Subject Terms:
maximum neighbourhood orderings, Extremal problems in graph theory, Duality, Analysis of algorithms and problem complexity, Applied Mathematics, Linear-time algorithm, 0102 computer and information sciences, chordal graphs, 01 natural sciences, Disk hypergraph, Trees, Hypertree, Strongly chordal graph, Location problem, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, dually chordal graphs, Tree structure, Discrete Mathematics and Combinatorics, Dually chordal graph, tree structure, Maximum neighbourhood ordering, graphic algorithms, Steiner tree
Document Type:
Book
Part of book or chapter of book<br />Article
File Description:
application/xml
ISSN:
0166-218X
DOI:
10.1007/3-540-59071-4_38
DOI:
10.1016/s0166-218x(97)00125-x
Access URL:
https://dblp.uni-trier.de/db/conf/wg/wg94.html#BrandstadtCD94
https://link.springer.com/chapter/10.1007/3-540-59071-4_38
https://rd.springer.com/chapter/10.1007/3-540-59071-4_38
https://dblp.uni-trier.de/db/journals/dam/dam82.html#BrandstadtCD98
https://www.sciencedirect.com/science/article/pii/S0166218X9700125X
https://link.springer.com/chapter/10.1007/3-540-59071-4_38
https://rd.springer.com/chapter/10.1007/3-540-59071-4_38
https://dblp.uni-trier.de/db/journals/dam/dam82.html#BrandstadtCD98
https://www.sciencedirect.com/science/article/pii/S0166218X9700125X
Rights:
Elsevier Non-Commercial
Accession Number:
edsair.doi.dedup.....80c52c9b5f5191f77a4a037b42b8f52b
Database:
OpenAIRE
Further Information
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.