BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Christophe Crespelle

Christophe Crespelle appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsDiscrete MathematicsComputational Complexitymath.CO

Catalog footprint

What is connected

5works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

5 published item(s)

preprint2022arXiv

A quasi-quadratic vertex Kernel for Cograph edge editing

We provide a $O(k^2 \mathrm{log} k)$ vertex kernel for cograph edge editing. This improves a cubic kernel found by Guillemot, Havet, Paul and Perez [1] which involved four reduction rules. We generalize one of their rules, based on packing of induced paths of length four, by introducing t-modules, which are modules up to t edge modifications. The key fact is that large t-modules cannot be edited more than t times, and this allows to obtain a near quadratic kernel. The extra $\mathrm{log} k$ factor seems tricky to remove as it is necessary in the combinatorial lemma on trees which is central in our proof. Nevertheless, we think that a quadratic bound should be reachable.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

On the Termination of Some Biclique Operators on Multipartite Graphs

We define a new graph operator, called the weak-factor graph, which comes from the context of complex network modelling. The weak-factor operator is close to the well-known clique-graph operator but it rather operates in terms of bicliques in a multipartite graph. We address the problem of the termination of the series of graphs obtained by iteratively applying the weak-factor operator starting from a given input graph. As for the clique-graph operator, it turns out that some graphs give rise to series that do not terminate. Therefore, we design a slight variation of the weak-factor operator, called clean-factor, and prove that its associated series terminates for all input graphs. In addition, we show that the multipartite graph on which the series terminates has a very nice combinatorial structure: we exhibit a bijection between its vertices and the chains of the inclusion order on the intersections of the maximal cliques of the input graph.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Termination of Multipartite Graph Series Arising from Complex Network Modelling

An intense activity is nowadays devoted to the definition of models capturing the properties of complex networks. Among the most promising approaches, it has been proposed to model these graphs via their clique incidence bipartite graphs. However, this approach has, until now, severe limitations resulting from its incapacity to reproduce a key property of this object: the overlapping nature of cliques in complex networks. In order to get rid of these limitations we propose to encode the structure of clique overlaps in a network thanks to a process consisting in iteratively factorising the maximal bicliques between the upper level and the other levels of a multipartite graph. We show that the most natural definition of this factorising process leads to infinite series for some instances. Our main result is to design a restriction of this process that terminates for any arbitrary graph. Moreover, we show that the resulting multipartite graph has remarkable combinatorial properties and is closely related to another fundamental combinatorial object. Finally, we show that, in practice, this multipartite graph is computationally tractable and has a size that makes it suitable for complex network modelling.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Faster and Enhanced Inclusion-Minimal Cograph Completion

We design two incremental algorithms for computing an inclusion-minimal completion of an arbitrary graph into a cograph. The first one is able to do so while providing an additional property which is crucial in practice to obtain inclusion-minimal completions using as few edges as possible : it is able to compute a minimum-cardinality completion of the neighbourhood of the new vertex introduced at each incremental step. It runs in $O(n+m')$ time, where $m'$ is the number of edges in the completed graph. This matches the complexity of the algorithm in [Lokshtanov, Mancini and Papadopoulos 2010] and positively answers one of their open questions. Our second algorithm improves the complexity of inclusion-minimal completion to $O(n+m\log^2 n)$ when the additional property above is not required. Moreover, we prove that many very sparse graphs, having only $O(n)$ edges, require $Ω(n^2)$ edges in any of their cograph completions. For these graphs, which include many of those encountered in applications, the improvement we obtain on the complexity scales as $O(n/\log^2 n)$.

0 citations0 reviewsNo code linkedOpen access