✦ LIBER ✦

Local medians in chordal graphs

✍ Scribed by Heiko Wittenberg

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 535 KB
Volume: 28
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(90)90009-2

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The w-median of a connected strongly cho

The w-median of a connected strongly chordal graph

✍ Hai-Yen Lee; Gerard J. Chang 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 337 KB 👁 1 views

## Abstract Suppose __G = (V, E)__ is a graph in which every vertex __x__ has a non‐negative real number __w(x)__ as its weight. The __w__‐distance sum of a vertex __y__ is __D~G, w~(y)__ = σ~x≅v~ __d(y, x)w(x).__ The __w__‐median of __G__ is the set of all vertices __y__ with minimum __w__‐distanc

Medians in median graphs

✍ H.J. Bandelt; J.P. Barthélemy 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 668 KB

Dominating cliques in chordal graphs

✍ Dieter Kratsch; Peter Damaschke; Anna Lubiw 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 492 KB

A chordal graph has a dominating clique iff it has diameter at most 3. A strongly chordal graph which has a dominating clique has one as small as the smallest dominating set-and, furthermore, there is a linear-time algorithm to find such a small dominating clique.

Independent domination in chordal graphs

✍ Martin Farber 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 460 KB

Matching and multidimensional matching i

Matching and multidimensional matching in chordal and strongly chordal graphs

✍ Elias Dahlhaus; Marek Karpinski 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 877 KB

Chordal graphs are graphs with the property that each cycle of length greater than 3 has two non-consecutive vertices that are joined by an edge. An important subclass of chordal graphs are strongly chordal graphs (Farber, 1983). Chordal graphs appear for example in the design of acyclic data base s

Hamiltonian circuits in chordal bipartit

Hamiltonian circuits in chordal bipartite graphs

✍ Haiko Müller 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 359 KB

The main result of this paper is the NP-completeness of the HAMILTONIAN CIRCUIT problem for chordal bipartite graphs. This is proved by a sophisticated reduction from SATISFIABILITY. As a corollary, HAMILTONIAN CIRCUIT is NP-complete for strongly chordal split graphs. On both classes the complexity