Source author record

Jérémie Dusart

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Artificial Intelligence Discrete Mathematics

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits

We are interested in computing $k$ most preferred models of a given d-DNNF circuit $C$ , where the preference relation is based on an algebraic structure called a monotone, totally ordered, semigroup $(K, \otimes, <)$ . In our setting, every literal in $C$ has a value in $K$ and the value of an assignment is an element of $K$ obtained by aggregating using $\otimes$ the values of the corresponding literals. We present an algorithm that computes $k$ models of $C$ among those having the largest values w.r.t. $<$ , and show that this algorithm runs in time polynomial in $k$ and in the size of $C$ . We also present a pseudo polynomial-time algorithm for deriving the top- $k$ values that can be reached, provided that an additional (but not very demanding) requirement on the semigroup is satisfied. Under the same assumption, we present a pseudo polynomial-time algorithm that transforms $C$ into a d-DNNF circuit $C'$ satisfied exactly by the models of $C$ having a value among the top- $k$ ones. Finally, focusing on the semigroup $(\mathbb{N}, +, <)$ , we compare on a large number of instances the performances of our compilation-based algorithm for computing $k$ top solutions with those of an algorithm tackling the same problem, but based on a partial weighted MaxSAT solver.

preprint2016arXiv

Maximal cliques structure for cocomparability graphs and applications

A cocomparability graph is a graph whose complement admits a transitive orientation. An interval graph is the intersection graph of a family of intervals on the real line. In this paper we investigate the relationships between interval and cocomparability graphs. This study is motivated by recent results Corneil,Dalton, Habib (2013) and Dusart, Habib (2016) and that show that for some problems, the algorithm used on interval graphs can also be used with small modifications on cocomparability graphs. Many of these algorithms are based on graph searches that preserve cocomparability orderings. First we propose a characterization of cocomparability graphs via a lattice structure on the set of their maximal cliques. Using this characterization we can prove that every maximal interval subgraph of a cocomparability graph $G$ is also a maximal chordal subgraph of $G$ . Although the size of this lattice of maximal cliques can be exponential in the size of the graph, it can be used as a framework to design and prove algorithms on cocomparability graphs. In particular we show that a new graph search, namely Local Maximal Neighborhood Search (LocalMNS) leads to an $O(n+mlogn)$ time algorithm to find a maximal interval subgraph of a cocomparability graph. Similarly we propose a linear time algorithm to compute all simplicial vertices in a cocomparability graph. In both cases we improve on the current state of knowledge.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.