✦ LIBER ✦

The obnoxious center problem on weighted cactus graphs

✍ Scribed by Blaž Zmazek; Janez Žerovnik

Publisher: Elsevier Science
Year: 2004
Tongue: English
Weight: 264 KB
Volume: 136
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(03)00452-9

No coin nor oath required. For personal study only.

✦ Synopsis

The obnoxious center problem in a graph G asks for a location on an edge of the graph such that the minimum weighted distance from this point to a vertex of the graph is as large as possible. An algorithm is given which ÿnds the obnoxious center on a weighted cactus graph in O(cn) time, where n is the number of vertices and c is the number of di erent vertex weights (called marks).

📜 SIMILAR VOLUMES

The obnoxious center problem on weighted

The obnoxious center problem on weighted cactus graphs (Extended Abstract)

✍ Blaž Zmazek; Janez Žerovnik 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 260 KB

The searchlight guarding problem on weig

The searchlight guarding problem on weighted split graphs and weighted cographs

✍ Yen, William C. K.; Tang, C. Y. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 223 KB 👁 2 views

This paper addresses the searchlight guarding problem, which is an extension of so-called graph searching/guarding problem on a weighted, undirected graph G by considering the time-slot parameter in addition to the traditional building cost. Given a weighted, undirected graph G G G, suppose that the

The weighted euclidean 1-center problem

✍ R. Chandrasekaran 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 204 KB

Solving the weighted efficient edge domi

Solving the weighted efficient edge domination problem on bipartite permutation graphs

✍ Chin Lung Lu; Chuan Yi Tang 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 666 KB

Given a simple graph G = (V, E), an edge (u, u) E E is said to dominate itself and any edge (u,x) or (u,x), where x E V. A subset D C E is called an efficient edge dominating set of G if all edges in E are dominated by exactly one edge of D. The efficient edge domination problem is to find an effici

The bi-criteria doubly weighted center-m

The bi-criteria doubly weighted center-median path problem on a tree

✍ J. Puerto; A.M. Rodríguez-Chía; A. Tamir; D. Pérez-Brito 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 248 KB

A linear-time algorithm for the weighted

A linear-time algorithm for the weighted feedback vertex problem on interval graphs

✍ Chin Lung Lu; Chuan Yi Tang 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 459 KB

We present a linear-time algorithm for finding a minimum weighted feedback vertex set on interval graphs using the dynamic programming technique. Since the weighted feedback vertex problem, the weighted C3.1 problem, the maximum weighted 2-colorable subgraph problem and the maximum weighted 2-indepe