On the inapproximability of independent domination in 2P3-free perfect graphs
Graph Chatbot
Chat with Graph Search
Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.
DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.
We are given a set script T = (T1, T2, . . . , Tk) of rooted binary trees, each Ti leaf-labeled by a subset L[Ti] C (1,2, . . . , n). If T is a tree on (1, 2, . . . , n), we let T|L denote the minimal subtree of T induced by the nodes of L and all their an ...
We deal with non-rank facets of the stable set polytope of claw-free graphs. We extend results of Giles and Trotter [7] by (i) showing that for any nonnegative integer a there exists a circulant graph whose stable set polytope has a facet-inducing inequali ...
This paper presents an approach to automatically extract and evaluate the ``stability'' of pronunciation variants (i.e., adequacy of the model to accommodate this variability), based on multiple pronunciations of each lexicon words and the knowledge of a r ...
Automatic failure-path inference (AFPI) is an application-generic, automatic technique for dynamically discovering the failure dependency graphs of componentized Internet applications. AFPI's first phase is invasive, and relies on controlled fault injectio ...
We deal with non-rank facets of the stable set polytope of claw-free graphs. We extend results of Gilles and Trotter (7) by (i) showing that for any nonnegative integer a there exists a circulant graph whose stable set polytope has a facet-inducing inequal ...
The problem of determining whether a graph G contains a threshold subgraph containing at least h edges is shown to be NP-complete if h is part of the input as the problems of minimum threshold completion, weighted 2-threshold partition and weighted 2-thres ...
Randomized stopping points form a convex set associated with the information structure that arises in the context of the optimal stopping problem for two-parameter processes. We study combinatorial properties of this structure when the underlying space is ...
The motivation to this research is the study of the optimal stopping problem for multiparameter processes : given a random process depending on finitely many parameters t = (t1,…,tn), which if stopped at point t in the parameter set produces a reward Xt, w ...
We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum ve ...
