Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Split (graph theory)

Related publications (10)

Microsimulation Framework for Urban Price-Taker Markets

Bilal Farooq

In the context of integrated transportation and other urban engineering infrastructure systems, there are many examples of markets, where consumers exhibit price-taking behaviour. While this behaviour is ubiquitous, the underlying mechanism can be captured ...

2013

d-Transversals of stable sets and vertex covers in weighted bipartite graphs

Dominique de Werra, Bernard Ries

Let G=(V,E)G=(V,E) be a graph in which every vertex v∈Vv∈V has a weight w(v)⩾0w(v)⩾0 and a cost c(v)⩾0c(v)⩾0. Let SGSG be the family of all maximum-weight stable sets in G . For any integer d⩾0d⩾0, a minimum d-transversal in the graph G with respect to SGS ...

2012

Minimum d-blockers and d-transversals in graphs

Dominique de Werra

We consider a set V of elements and an optimization problem on V: the search for a maximum (or minimum) cardinality subset of V verifying a given property a"similar to. A d-transversal is a subset of V which intersects any optimum solution in at least d el ...

2011

Split-critical and uniquely split-colorable graphs

Dominique de Werra, Tinaz Ekim, Bernard Ries

The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring p ...

2010

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Dominique de Werra

We study complexity and approximation of MIN WEIGHTED NODE COLORING in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove ...

2009

Coloring Fuzzy Circular Interval Graphs

Friedrich Eisenbrand, Martin Niemeier

Computing the weighted coloring number of graphs is a classical topic in combinatorics and graph theory. Recently these problems have again attracted a lot of attention for the class of quasi-line graphs and more specifically fuzzy circular interval graphs ...

Elsevier2009

Polar cographs

Dominique de Werra, Tinaz Ekim

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s, k)-polar if there exists a partition A, B of its vertex set such that A induces a complete s-partite grap ...

Elsevier2008

Some coloring and walking problems in graphs

Benjamin Leroy-Beaulieu

Graph theory is an important topic in discrete mathematics. It is particularly interesting because it has a wide range of applications. Among the main problems in graph theory, we shall mention the following ones: graph coloring and the Hamiltonian circuit ...

EPFL2008

Generalized vertex coloring problems using split graphs

Tinaz Ekim

Graph theory experienced a remarkable increase of interest among the scientific community during the last decades. The vertex coloring problem (Min Coloring) deserves a particular attention rince it has been able to capture a wide variety of applications. ...

EPFL2006

Suboptimal colorings and solution of large chromatic scheduling problems

Ivo Blöchliger

Graph Coloring is a very active field of research in graph theory as well as in the domain of the design of efficient heuristics to solve problems which, due to their computational complexity, cannot be solved exactly (no guarantee that an optimal solution ...

EPFL2005

Related publications (10)