29 citations · 92 across the 53 of their papers we have counts for
5 papers · 1 filter
On Communication Complexity of Fixed Point Computation
Anat Ganor, Karthik C. S., Dömötör Pálvölgyi
Brouwer's fixed point theorem states that any continuous function from a compact convex space to itself has a fixed point. Roughgarden and Weinstein (FOCS 2016) initiated the study…
Acyclic orientations with degree constraints
Zoltán Király, Dömötör Pálvölgyi
In this note we study the complexity of some generalizations of the notion of -numbering. Suppose that given some functions and , we want to order the vertices of a grap…
Complexity of Domination in Triangulated Plane Graphs
Dömötör Pálvölgyi
We prove that for a triangulated plane graph it is NP-complete to determine its domination number and its power domination number.
Communication Complexity
Dömötör Pálvölgyi
The first section starts with the basic definitions following mainly the notations of the book written by E. Kushilevitz and N. Nisan. At the end of the first section I examine tre…
Partitionability to two trees is NP-complete
Domotor Palvolgyi
We show that P2T - the problem of deciding whether the edge set of a simple graph can be partitioned into two trees or not - is NP-complete.