The algorithmic use of hypertree structure and maximum neighbourhood orderings

DOI10.1016/S0166-218X(97)00125-XzbMath0893.05018OpenAlexW2013215731MaRDI QIDQ1383368

Victor Chepoi, Andreas Brandstädt, Feodor F. Dragan

Publication date: 2 August 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

chordal graphsSteiner treedually chordal graphsgraphic algorithmstree structuremaximum neighbourhood orderings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (39)

Complexity issues of perfect secure domination in graphs ⋮ Detour trees ⋮ Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ How to use spanning trees to navigate in graphs ⋮ NP-completeness of the \(\{k \}\)-packing function problem in graphs ⋮ Algorithmic aspects of open neighborhood location-domination in graphs ⋮ 3-colouring for dually chordal graphs and generalisations ⋮ Complexity aspects of variants of independent Roman domination in graphs ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Unique response Roman domination: complexity and algorithms ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ On Strong Tree-Breadth ⋮ Cosecure domination: hardness results and algorithms ⋮ Some new algorithmic results on co-secure domination in graphs ⋮ On the complexity of the {k}-packing function problem ⋮ \(L(2,1)\)-labeling of dually chordal graphs and strongly orderable graphs ⋮ Global total \(k\)-domination: approximation and hardness results ⋮ Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs ⋮ Wiener Index of Hypertree ⋮ Improved Bound for Dilation of an Embedding onto Circulant Networks ⋮ Variations of \(Y\)-dominating functions on graphs ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ Small \(k\)-pyramids and the complexity of determining \(k\) ⋮ On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem ⋮ Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs ⋮ Diameter determination on restricted graph families ⋮ Parameterized approximation algorithms for some location problems in graphs ⋮ Dominating sets reconfiguration under token sliding ⋮ Algorithmic aspects of secure connected domination in graphs ⋮ Algorithmic aspects of 2-secure domination in graphs ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Algorithms and Complexity of Signed, Minus, and Majority Domination ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ On the algorithmic complexity of twelve covering and independence parameters of graphs ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs ⋮ Coloring squares of graphs via vertex orderings ⋮ On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs ⋮ Fast Diameter Computation within Split Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Characterizations of strongly chordal graphs
• A characterization of totally balanced hypergraphs
• A heuristic for the p-center problem in graphs
• On domination problems for permutation and other graphs
• Labeling algorithms for domination problems in sun-free chordal graphs
• Topics on domination
• Dominating cliques in chordal graphs
• Treewidth. Computations and approximations
• \(r\)-dominating cliques in graphs with hypertree structure
• Time bounds for selection
• Domination in quadrangle-free Helly graphs
• A characterisation of rigid circuit graphs
• Doubly lexical ordering of dense 0--1 matrices
• Normal hypergraphs and the perfect graph conjecture
• A Class of Balanced Matrices Arising from Location Problems
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Steiner trees, connected domination and strongly chordal graphs
• Doubly Lexical Orderings of Matrices
• Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
• Three Partition Refinement Algorithms
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• Location on Tree Networks: P-Centre and n-Dispersion Problems
• Algorithmic Aspects of Vertex Elimination on Graphs
• `` Strong NP-Completeness Results
• Clique Graphs of Chordal and Path Graphs
• Doubly chordal graphs, steiner trees, and connected domination
• Algorithmic Aspects of Neighborhood Numbers

This page was built for publication: The algorithmic use of hypertree structure and maximum neighbourhood orderings