BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Martin Vatshelle

Martin Vatshelle contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDiscrete MathematicsComputational Complexitymath.CO

Trust snapshot

Quick read

Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

3 published item(s)

preprint2022arXiv

Recognition of Linear and Star Variants of Leaf Powers is in P

A $k$-leaf power of a tree $T$ is a graph $G$ whose vertices are the leaves of $T$ and whose edges connect pairs of leaves whose distance in $T$ is at most $k$. A graph is a leaf power if it is a $k$-leaf power for some $k$. Over 20 years ago, Nishimura et al. [J. Algorithms, 2002] asked if recognition of leaf powers was in P. Recently, Lafond [SODA 2022] showed an XP algorithm when parameterized by $k$, while leaving the main question open. In this paper, we explore this question from the perspective of two alternative models of leaf powers, showing that both a linear and a star variant of leaf powers can be recognized in polynomial-time.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

k-Gap Interval Graphs

We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real line, with an edge between two vertices if and only if an interval associated to one vertex has a nonempty intersection with an interval associated to the other vertex. A graph on n vertices is a k-gap interval graph if it has a multiple interval representation with at most n+k intervals in total. In order to scale up the nice algorithmic properties of interval graphs (where k=0), we parameterize graph problems by k, and find FPT algorithms for several problems, including Feedback Vertex Set, Dominating Set, Independent Set, Clique, Clique Cover, and Multiple Interval Transversal. The Coloring problem turns out to be W[1]-hard and we design an XP algorithm for the recognition problem.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On graph classes with logarithmic boolean-width

Boolean-width is a recently introduced graph parameter. Many problems are fixed parameter tractable when parametrized by boolean-width, for instance "Minimum Weighted Dominating Set" (MWDS) problem can be solved in $O^*(2^{3k})$ time given a boolean-decomposition of width $k$, hence for all graph classes where a boolean-decomposition of width $O(\log n)$ can be found in polynomial time, MWDS can be solved in polynomial time. We study graph classes having boolean-width $O(\log n)$ and problems solvable in $O^*(2^{O(k)})$, combining these two results to design polynomial algorithms. We show that for trapezoid graphs, circular permutation graphs, convex graphs, Dilworth-$k$ graphs, circular arc graphs and complements of $k$-degenerate graphs, boolean-decompositions of width $O(\log n)$ can be found in polynomial time. We also show that circular $k$-trapezoid graphs have boolean-width $O(\log n)$, and find such a decomposition if a circular $k$-trapezoid intersection model is given. For many of the graph classes we also prove that they contain graphs of boolean-width $Θ(\log n)$. Further we apply the results from \cite{boolw2} to give a new polynomial time algorithm solving all vertex partitioning problems introduced by Proskurowski and Telle \cite{TP97}. This extends previous results by Kratochvíl, Manuel and Miller \cite{KMM95} showing that a large subset of the vertex partitioning problems are polynomial solvable on interval graphs.

0 citations0 reviewsNo code linkedOpen access