Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userClasses of intersection digraphs with good algorithmic properties
96
0
0.0
(
0
)
Added by
Lars Jaffke
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
An intersection digraph is a digraph where every vertex $v$ is represented by an ordered pair $(S_v, T_v)$ of sets such that there is an edge from $v$ to $w$ if and only if $S_v$ and $T_w$ intersect. An intersection digraph is reflexive if $S_vcap T_v eq emptyset$ for every vertex $v$. Compared to well-known undirected intersection graphs like interval graphs and permutation graphs, not many algorithmic applications on intersection digraphs have been developed. Motivated by the successful story on algorithmic applications of intersection graphs using a graph width parameter called mim-width, we introduce its directed analogue called `bi-mim-width and prove that various classes of reflexive intersection digraphs have bounded bi-mim-width. In particular, we show that as a natural extension of $H$-graphs, reflexive $H$-digraphs have linear bi-mim-width at most $12|E(H)|$, which extends a bound on the linear mim-width of $H$-graphs [On the Tractability of Optimization Problems on $H$-Graphs. Algorithmica 2020]. For applications, we introduce a novel framework of direct
rate research
Read More
We discuss transpose (sometimes called universal exchange or all-to-all) on vertex symmetric networks. We provide a method to compare the efficiency of transpose schemes on two different networks with a cost function based on the number processors and wires needed to complete a given algorithm in a given time.
A dicut in a directed graph is a cut for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of a set of edges meeting every non-empty dicut equals the maximum number of disjoint dicuts in that digraph. Such sets are called dijoins. Woodall conjectured a dual statement. He asked whether the maximum number of disjoint dijoins in a directed graph equals the minimum size of a non-empty dicut. We study a modification of this question where we restrict our attention to certain classes of non-empty dicuts, i.e. whether for a class $mathfrak{B}$ of dicuts of a directed graph the maximum number of disjoint sets of edges meeting every dicut in $mathfrak{B}$ equals the size of a minimum dicut in $mathfrak{B}$. In particular, we verify this questions for nested classes of finite dicuts, for the class of dicuts of minimum size, and for classes of infinite dibonds, and we investigate how this generalised setting relates to a capacitated version of this question.
There has been substantial interest in estimating the value of a graph parameter, i.e., of a real-valued function defined on the set of finite graphs, by querying a randomly sampled substructure whose size is independent of the size of the input. Graph parameters that may be successfully estimated in this way are said to be testable or estimable, and the sample complexity $q_z=q_z(epsilon)$ of an estimable parameter $z$ is the size of a random sample of a graph $G$ required to ensure that the value of $z(G)$ may be estimated within an error of $epsilon$ with probability at least 2/3. In this paper, for any fixed monotone graph property $mathcal{P}=mbox{Forb}(mathcal{F})$, we study the sample complexity of estimating a bounded graph parameter $z_{mathcal{P}}$ that, for an input graph $G$, counts the number of spanning subgraphs of $G$ that satisfy $mathcal{P}$. To improve upon previous upper bounds on the sample complexity, we show that the vertex set of any graph that satisfies a monotone property $mathcal{P}$ may be partitioned equitably into a constant number of classes in such a way that the cluster graph induced by the partition is not far from satisfying a natural weighted graph generalization of $mathcal{P}$. Properties for which this holds are said to be recoverable, and the study of recoverable properties may be of independent interest.
We study an assignment system of intersection types for a lambda-calculus with records and a record-merge operator, where types are preserved both under subject reduction and expansion. The calculus is expressive enough to naturally represent mixins as functions over recursively defined classes, whose fixed points, the objects, are recursive records. In spite of the double recursion that is involved in their definition, classes and mixins can be meaningfully typed without resorting to neither recursive nor F-bounded polymorphic types. We then adapt mixin construct and composition to Java and C#, relying solely on existing features in such a way that the resulting code remains typable in the respective type systems. We exhibit some example code, and study its typings in the intersection type system via interpretation into the lambda-calculus with records we have proposed.
We prove a conjecture of Fox, Huang, and Lee that characterizes directed graphs that have constant density in all tournaments: they are disjoint unions of trees that are each constructed in a certain recursive way.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
