Matthieu Petiteau

collaborators

Showing cs.DMShow all

2 papers · 1 filter

cs.DM2026

Some polynomial classes for the acyclic orientation with parity constraint problem

Sylvain Gravier, Matthieu Petiteau, Isabelle Sivignon

We study the problem of finding an acyclic orientation of an undirected graph with constrained in-degree parities specified by a subset T of vertices. An orientation is called T -o…

cs.DM2025

Note about the complexity of the acyclic orientation with parity constraint problem

Sylvain Gravier, Matthieu Petiteau, Isabelle Sivignon

Let $G = (V, E)$ be a connected graph, and let $T$ in $V$ be a subset of vertices. An orientation of $G$ is called $T$ -odd if any vertex $v \in V$ has odd in-degree if and only if…