Cover Image

Optimized Degree Realization: Minimum Dominating Set & Maximum Matching

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bar-Noy, Amotz, Kalinichev, Igor, Peleg, David, Rawitz, Dror
Format:	Preprint
Published:	2025
Subjects:	Discrete Mathematics Data Structures and Algorithms 05C07, 68R10 G.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Degree Realization by Bipartite Cactus Graphs
by: Bar-Noy, Amotz, et al.
Published: (2025)

Degree Realization by Bipartite Multigraphs
by: Bar-Noy, Amotz, et al.
Published: (2025)

Approximate Realizations for Outerplanaric Degree Sequences
by: Bar-Noy, Amotz, et al.
Published: (2024)

On the thinness of trees
by: Bonomo-Braberman, Flavia, et al.
Published: (2025)

Searching in trees with monotonic query times
by: Dereniowski, Dariusz, et al.
Published: (2024)

Deterministic Minimum Steiner Cut in Maximum Flow Time
by: Ding, Matthew, et al.
Published: (2023)

Interval Graphs are Reconstructible
by: Heinrich, Irene, et al.
Published: (2025)

A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus
by: Sun, Hao
Published: (2023)

Adjacency Labeling Schemes for Small Classes
by: Bonnet, Édouard, et al.
Published: (2024)

The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
by: Laekhanukit, Bundit
Published: (2024)

A Tight Meta-theorem for LOCAL Certification of MSO$_2$ Properties within Bounded Treewidth Graphs
by: Cook, Linda, et al.
Published: (2025)

Posets are easily testable
by: Fekete, Panna Tímea, et al.
Published: (2023)

Fairness in the k-Server Problem
by: Daneshvaramoli, Mohammadreza, et al.
Published: (2025)

Enumeration of Bases in Matroid with Exponentially Large Ground Set
by: Nishimura, Yuki, et al.
Published: (2025)

On Relaxation of Dominant Sets
by: Koster, Max
Published: (2022)

Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs
by: Gabryelski, Wojciech, et al.
Published: (2026)

Pliability and Approximating Max-CSPs
by: Romero, Miguel, et al.
Published: (2019)

Highly Connected Steiner Subgraph -- Parameterized Algorithms and Applications to Hitting Set Problems
by: Eiben, Eduard, et al.
Published: (2023)

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
by: Bonnet, Édouard, et al.
Published: (2026)

Online Bipartite Matching in the Probe-Commit Model
by: Borodin, Allan, et al.
Published: (2023)

Online Matching and Contention Resolution for Edge Arrivals with Vanishing Probabilities
by: Ma, Will, et al.
Published: (2024)

Exact Minimum Weight Spanners via Column Generation
by: Bökler, Fritz, et al.
Published: (2024)

Temporalizing digraphs via linear-size balanced bi-trees
by: Bessy, Stéphane, et al.
Published: (2023)

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
by: Bonnet, Édouard, et al.
Published: (2023)

Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
by: Buchbinder, Niv, et al.
Published: (2024)

On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
by: MacRury, Calum, et al.
Published: (2022)

APTAS for bin packing with general cost structures
by: Jaykrishnan, G., et al.
Published: (2024)

Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
by: Komusiewicz, Christian, et al.
Published: (2023)

Faster algorithms on linear delta-matroids
by: Koana, Tomohiro, et al.
Published: (2024)

A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees
by: Jacob, Ashwin, et al.
Published: (2026)

Partial Implementation of Max Flow and Min Cost Flow in Almost-Linear Time
by: Kavi, Nithin
Published: (2024)

On the Parameterized Tractability of Packing Vertex-Disjoint A-Paths with Length Constraints
by: Bandopadhyay, Susobhan, et al.
Published: (2026)

Searching in trees with $k$-up-modular cost functions
by: Szyfelbein, Michał
Published: (2025)

A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees
by: Jacob, Ashwin, et al.
Published: (2024)

Directed Capacity-Preserving Subgraphs: Hardness and Exact Polynomial Algorithms
by: Chimani, Markus, et al.
Published: (2023)

Killing a Vortex
by: Thilikos, Dimitrios M., et al.
Published: (2022)

Bicriteria Submodular Maximization
by: Feldman, Moran, et al.
Published: (2025)

Forward-backward Contention Resolution Schemes for Fair Rationing
by: Ma, Will, et al.
Published: (2025)