Péter Madarasi

activity

20192026

most citedMatchings under distance constraints I

2 citations · 2 across the 15 of their papers we have counts for

collaborators

17 papers

cs.DM2026

Complexity, approximation, and extension of proper ${a, b}$ -edge-weightings

Péter Madarasi, Máté Simon

For distinct integers $a$ and $b$ , an ${a, b}$ -edge-weighting assigns $a$ or $b$ to each edge and labels each vertex by the sum of its incident weights. Such a weighting is proper…

math.CO2026

Proper ${a, b}$ -edge-weightings of trees

Péter Madarasi

Let $a$ and $b$ be distinct real weights. An ${a, b}$ -edge-weighting of a tree assigns one of these weights to each edge and is proper if adjacent vertices have different sums of…

cs.GT2026

The Complexity of Kemeny Aggregation with Three Rankings

Péter Madarasi

The Kemeny rule aggregates rankings by minimizing their total Kendall-tau distance from an aggregate order. We prove that Kemeny Score is NP-complete for exactly three unweighted r…

cs.DS2026

Temporal matching in trees

Márk Hunor Juhász, Péter Madarasi

We study maximum matching problems in temporal graphs whose underlying graph is a tree. We consider two temporal models. In a $Δ$ -matching, selected time edges sharing an endpoint…

cs.DS2026

Asymptotically Faster Algorithms for Recognizing $(k, ℓ)$ -Sparse Graphs

Bence Deák, Péter Madarasi

For fixed integers $k, ℓ$ with $0 \leq ℓ < 3 k$ , we study the problem of deciding whether a graph is $(k, ℓ)$ -sparse, a notion arising in combinatorial optimization and rigidity…

math.CO2026

Polytopes of alternating sign matrices with dihedral symmetries

Péter Madarasi

We study the convex hulls of $n \times n$ alternating sign matrices invariant under subgroups of the dihedral group of the square. For each non-trivial symmetry class, the symmetry…

cs.DS2025

Quadratic-Time Algorithm for the Maximum-Weight $(k, ℓ)$ -Sparse Subgraph Problem

Bence Deák, Péter Madarasi

The family of $(k, ℓ)$ -sparse graphs, introduced by Lorea, plays a central role in combinatorial optimization and has a wide range of applications, particularly in rigidity theo…

cs.DS2025

Efficient Algorithms and Implementations for Extracting Maximum-Size $(k, ℓ)$ -Sparse Subgraphs

Péter Madarasi

A multigraph $G = (V, E)$ is $(k, ℓ)$ -sparse if every subset $X \subseteq V$ induces at most $max {k ∣ X ∣ - ℓ, 0}$ edges. Finding a maximum-size $(k, ℓ)$ -sparse subgraph i…

math.CO2025

Separable convex optimization over indegree polytopes

Nóra A. Borsik, Péter Madarasi

We study separable discrete convex optimization over indegree vectors of orientations of an undirected graph, focusing on the effect of imposing acyclicity. Since the extreme point…

math.CO2025

Vertex-ordering and arc-partitioning problems

Nóra A. Borsik, Péter Madarasi

We study vertex-ordering problems in loop-free digraphs subject to constraints on the left-going arcs, focusing on existence conditions and computational complexity. As an intrigui…

cs.DS2025

Simultaneous Network Design with Restricted Link Usage

Naonori Kakimura, Péter Madarasi, Jannik Matuschke +1

Given a digraph with two terminal vertices $s$ and $t$ as well as a conservative cost function and several not necessarily disjoint color classes on its arc set, our goal is to fin…

math.CO2025

Prefix-bounded matrices

Nóra A. Borsik, András Frank, Péter Madarasi +1

By unifying various earlier extensions of alternating sign matrices (ASMs), we introduce the notion of prefix-bounded matrices (PBMs). It is shown that the convex hull of these mat…

cs.DS2023

A graph isomorphism invariant based on neighborhood aggregation

Alpár Jüttner, Péter Madarasi

This paper presents a new graph isomorphism invariant, called $w$ -labeling, that can be used to design a polynomial-time algorithm for solving the graph isomorphism prob…

cs.DM2023

Matchings under distance constraints II

Péter Madarasi

This paper introduces the \emph{ $d$ -distance $b$ -matching problem}, in which we are given a bipartite graph $G = (S, T; E)$ with $S = {s_{1}, \dots, s_{n}}$ , a weight function on the edges,…

cs.DS2021

The Simultaneous Assignment Problem

Péter Madarasi

This paper introduces the Simultaneous assignment problem. Let us given a graph with a weight and a capacity function on its edges, and a set of its subgraphs along with a degree u…

math.CO2020

The Ramsey number of a long cycle and complete graphs

Péter Madarasi

In this paper, we prove that the multicolored Ramsey number $R (G_{1}, \dots, G_{n}, K_{n_{1}}, \dots, K_{n_{r}})$ is at least $(γ - 1) (κ - 1) + 1$ for arbitrary connected graphs $G_{1}, \dots, G_{n}$ and $…

math.CO2019★ 2 cited

Matchings under distance constraints I

Péter Madarasi

This paper introduces the \emph{ $d$ -distance matching problem}, in which we are given a bipartite graph $G = (S, T; E)$ with $S = {s_{1}, \dots, s_{n}}$ , a weight function on the edges and a…

Complexity, approximation, and extension of proper {a,b}-edge-weightings

Proper {a,b}-edge-weightings of trees

The Complexity of Kemeny Aggregation with Three Rankings

Temporal matching in trees

Asymptotically Faster Algorithms for Recognizing (k,ℓ)-Sparse Graphs

Polytopes of alternating sign matrices with dihedral symmetries

Quadratic-Time Algorithm for the Maximum-Weight (k,ℓ)-Sparse Subgraph Problem

Efficient Algorithms and Implementations for Extracting Maximum-Size (k,ℓ)-Sparse Subgraphs

Separable convex optimization over indegree polytopes

Vertex-ordering and arc-partitioning problems

Simultaneous Network Design with Restricted Link Usage

Prefix-bounded matrices

A graph isomorphism invariant based on neighborhood aggregation

Matchings under distance constraints II

The Simultaneous Assignment Problem

The Ramsey number of a long cycle and complete graphs

Matchings under distance constraints I

Complexity, approximation, and extension of proper ${a, b}$ -edge-weightings

Proper ${a, b}$ -edge-weightings of trees

Asymptotically Faster Algorithms for Recognizing $(k, ℓ)$ -Sparse Graphs

Quadratic-Time Algorithm for the Maximum-Weight $(k, ℓ)$ -Sparse Subgraph Problem

Efficient Algorithms and Implementations for Extracting Maximum-Size $(k, ℓ)$ -Sparse Subgraphs