Publications related to A note on chromatic properties of threshold graphs

The Exact Hausdorff Measure of the Zero Set of Fractional Brownian Motion

Let {X(t), t is an element of R-N} be a fractional Brownian motion in R-d of index H. If L(0,I) is the local time of X at 0 on the interval I subset of R-N, then there exists a positive finite constant c(=c(N,d,H)) such that ...

Springer US2011

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

Paolo Ienne, Philip Brisk, Ajay Kumar Verma

An optimal linear-time algorithm for interprocedural register allocation in high level synthesis is presented. Historically, register allocation has been modeled as a graph coloring problem, which is nondeterministic polynomial time-complete in general; ho ...

2010

The potential to improve the choice: list conflict-free coloring for geometric hypergraphs

Shakhar Smorodinsky

Given a geometric hypergraph (or a range-space)

H=(V,\cal E)

, a coloring of its vertices is said to be conflict-free if for every hyperedge

S \in \cal E

there is at least one vertex in

S

whose color is distinct from the colors of all other vertices i ...

2010

Coloring axis-parallel rectangles

János Pach, Gábor Tardos

For every k and r, we construct a finite family of axis-parallel rectangles in the plane such that no matter how we color them with k colors, there exists a point covered by precisely r members of the family, all of which have the same color. For r = 2, th ...

2010

MARGIN: Maximal frequent subgraph mining

Ramachandra Satyanarayana Valluri

The exponential number of possible subgraphs makes the problem of frequent subgraph mining a challenge. The set of maximal frequent subgraphs is much smaller to that of the set of frequent subgraphs providing ample scope for pruning. MARGIN is a maximal su ...

2010

Graph coloring with cardinality constraints on the neighborhoods

Dominique de Werra, Bernard Ries

Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph G a k-coloring, i.e., a partition V-1,...,V-k of the vertex set of G such that, for some specified neighborhood (N) over ...

2009

Partitioning graphs into complete and empty graphs

Tinaz Ekim

Given integers j and k and a graph G, we consider partitions of the vertex set of G into j + k parts where j of these parts induce empty graphs and the remaining k induce cliques. If such a partition exists, we say G is a (j, k)-graph. For a fixed j and k ...

2009

A property of Bp(G). Applications to convolution operators

Antoine Derighetti

A new property of B-p(G), permits to obtain an approximation theorem for p-convolution operators and a non-commutative version of the Lohoues monomorphism theorem concerning the norm closure of the set of all p-convolution operators with compact support. ( ...

2009

Optimistic chordal coloring: a coalescing heuristic for SSA form programs

Paolo Ienne, Philip Brisk, Ajay Kumar Verma

The interference graph for a procedure in Static Single Assignment (SSA) Form is chordal. Since the k-colorability problem can be solved in polynomial-time for chordal graphs, this result has generated interest in SSA-based heuristics for spilling and coal ...

Springer US2009

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

A note on chromatic properties of threshold graphs

Graph Chatbot

Chat with Graph Search

The Exact Hausdorff Measure of the Zero Set of Fractional Brownian Motion

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

The potential to improve the choice: list conflict-free coloring for geometric hypergraphs

Coloring axis-parallel rectangles

MARGIN: Maximal frequent subgraph mining

Graph coloring with cardinality constraints on the neighborhoods

Partitioning graphs into complete and empty graphs

A property of Bp(G). Applications to convolution operators

Optimistic chordal coloring: a coalescing heuristic for SSA form programs

Some coloring and walking problems in graphs

The Exact Hausdorff Measure of the Zero Set of Fractional Brownian Motion

Graph coloring with cardinality constraints on the neighborhoods

Some coloring and walking problems in graphs

Coloring axis-parallel rectangles

A property of Bp(G). Applications to convolution operators

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

The potential to improve the choice: list conflict-free coloring for geometric hypergraphs

MARGIN: Maximal frequent subgraph mining

Partitioning graphs into complete and empty graphs

Optimistic chordal coloring: a coalescing heuristic for SSA form programs