6 citations · 9 across the 9 of their papers we have counts for
4 papers · 1 filter
On the Complexity Landscape of Connected f -Factor Problems
R. Ganian, N. S. Narayanaswamy, S. Ordyniak +2
Let G be an undirected simple graph having n vertices and let f be a function defined to be f:V(G) -> {0,..., n-1}. An f-factor of G is a spanning subgraph H such that degree of a…
A New Perspective on FO Model Checking of Dense Graph Classes
Jakub Gajarský, Petr Hliněný, Daniel Lokshtanov +2
We study the first-order (FO) model checking problem of dense graphs, namely those which have FO interpretations in (or are FO transductions of) some sparse graph classes. We give…
Alternative parameterizations of Metric Dimension
Gregory Gutin, M. S. Ramanujan, Felix Reidl +1
A set of vertices in a graph is called resolving if for any two distinct , there is such that , where ${\rm di…
Reducing CMSO Model Checking to Highly Connected Graphs
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh +1
Given a Counting Monadic Second Order (CMSO) sentence , the CMSO problem is defined as follows. The input to CMSO is a graph , and the objective is to determine whe…