Results 61 to 70 of about 3,161 (171)
On first-order transductions of classes of graphs [PDF]
Logical Methods in Computer ScienceWe study various aspects of the first-order transduction quasi-order on graph classes, which provides a way of measuring the relative complexity of graph classes based on whether one can encode the other using a formula of first-order (FO) logic.
Samuel Braunfeld +3 more
doaj +1 more source
Discrete Mathematics & Theoretical Computer ScienceNot every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward $k$-planar drawings of DAGs in which the
Patrizio Angelini +10 more
doaj +1 more source
Outerplanar Obstructions for Matroid Pathwidth
Electronic Notes in Discrete Mathematics, 2011 For each non-negative integer k, we provide all outerplanar obstructions for the class of graphs whose cycle matroid has pathwidth at most k. Our proof combines a decomposition lemma for proving lower bounds on matroid pathwidth and a relation between matroid pathwidth and linear width.
Koichi Yamazaki +3 more
openaire +7 more sources
Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
Algorithms, 2018 Treedepth is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this ...
Li-Hsuan Chen +3 more
doaj +1 more source
The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
, 2014 We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex ...
Hatanaka, Tatsuhiko +2 more
core +1 more source
Structural parameterizations for boxicity [PDF]
, 2014 The boxicity of a graph $G$ is the least integer $d$ such that $G$ has an intersection model of axis-aligned $d$-dimensional boxes. Boxicity, the problem of deciding whether a given graph $G$ has boxicity at most $d$, is NP-complete for every fixed $d ...
A Adiga +19 more
core +1 more source
On the pathwidth of chordal graphs
Discrete Applied Mathematics, 1993 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +2 more sources
A simple linear-time algorithm for finding path-decompositions of small width [PDF]
, 1994 We described a simple algorithm running in linear time for each fixed constant $k$, that either establishes that the pathwidth of a graph $G$ is greater than $k$, or finds a path-decomposition of $G$ of width at most $O(2^{k})$.
Cattell, Kevin +2 more
core
An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains
, 2012 It is known that the First-Fit algorithm for partitioning a poset P into chains uses relatively few chains when P does not have two incomparable chains each of size k. In particular, if P has width w then Bosek, Krawczyk, and Szczypka (SIAM J.
Bosek B. +8 more
core +1 more source
Digraph Complexity Measures and Applications in Formal Language Theory [PDF]
, 2011 We investigate structural complexity measures on digraphs, in particular the cycle rank. This concept is intimately related to a classical topic in formal language theory, namely the star height of regular languages.
Hermann Gruber +1 more
core +4 more sources