2 citations · 2 across the 15 of their papers we have counts for
6 papers · 1 filter
Quadratic-Time Algorithm for the Maximum-Weight -Sparse Subgraph Problem
Bence Deák, Péter Madarasi
The family of -sparse graphs, introduced by Lorea, plays a central role in combinatorial optimization and has a wide range of applications, particularly in rigidity theo…
Efficient Algorithms and Implementations for Extracting Maximum-Size -Sparse Subgraphs
Péter Madarasi
A multigraph is -sparse if every subset induces at most edges. Finding a maximum-size -sparse subgraph i…
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…
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…
Simultaneous Network Design with Restricted Link Usage
Naonori Kakimura, Péter Madarasi, Jannik Matuschke +1
Given a digraph with two terminal vertices and as well as a conservative cost function and several not necessarily disjoint color classes on its arc set, our goal is to fin…
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…