Page 1

Displaying 1 – 2 of 2

Showing per page

Balanced problems on graphs with categorization of edges

Štefan Berežný, Vladimír Lacko (2003)

Discussiones Mathematicae Graph Theory

Suppose a graph G = (V,E) with edge weights w(e) and edges partitioned into disjoint categories S₁,...,Sₚ is given. We consider optimization problems on G defined by a family of feasible sets (G) and the following objective function: L ( D ) = m a x 1 i p ( m a x e S i D w ( e ) - m i n e S i D w ( e ) ) For an arbitrary number of categories we show that the L₅-perfect matching, L₅-a-b path, L₅-spanning tree problems and L₅-Hamilton cycle (on a Halin graph) problem are NP-complete. We also summarize polynomiality results concerning above objective functions for arbitrary...

Block decomposition approach to compute a minimum geodetic set

Tınaz Ekim, Aysel Erey (2014)

RAIRO - Operations Research - Recherche Opérationnelle

In this paper, we develop a divide-and-conquer approach, called block decomposition, to solve the minimum geodetic set problem. This provides us with a unified approach for all graphs admitting blocks for which the problem of finding a minimum geodetic set containing a given set of vertices (g-extension problem) can be efficiently solved. Our method allows us to derive linear time algorithms for the minimum geodetic set problem in (a proper superclass of) block-cacti and monopolar chordal graphs....

Currently displaying 1 – 2 of 2

Page 1