error
Kurzer Serviceunterbruch am Donnerstag, 16. April 2026, 12 bis 13 Uhr. Sie können in diesem Zeitraum keine neuen Dokumente hochladen oder bestehende Einträge bearbeiten. Das Login wird in diesem Zeitraum deaktiviert. Grund: Wartungsarbeiten // Short service interruption on Thursday, April 16, 2026, 12.00 – 13.00. During this time, you won’t be able to upload new documents or edit existing records. The login will be deactivated during this time. Reason: maintenance work
 

Journal: Discrete Applied Mathematics

Abbreviation

Discrete Appl. Math.

Publisher

Elsevier

Journal Volumes

ISSN

0166-218X
1872-6771

Description

Filters

Reset filters

Search Results

Publications1 - 10 of 27
  • Assistance and interdiction problems on interval graphs
    Item type: Journal Article
    Hoang, Hung P.; Lendl, Stefan; Wulf, Lasse (2023)
    Discrete Applied Mathematics
    We introduce a novel framework of graph modifications specific to interval graphs. We study interdiction problems with respect to these graph modifications. Given a list of original intervals, each interval has a replacement interval such that either the replacement contains the original, or the original contains the replacement. The interdictor is allowed to replace up to k original intervals with their replacements. Using this framework we also study the contrary of interdiction problems which we call assistance problems. We study these problems for the independence number, the clique number, shortest paths, and the scattering number. We obtain polynomial time algorithms for most of the studied problems. Via easy reductions, it follows that on interval graphs, the most vital nodes problem with respect to shortest path, independence number and Hamiltonicity can be solved in polynomial time.
  • Opinion forming in Erdős–Rényi random graph and expanders
    Item type: Journal Article
    Zehmakan, Ahad N. (2020)
    Discrete Applied Mathematics
    Assume for a graph G=V,E and an initial configuration, where each node is blue or red, in each discrete-time round all nodes simultaneously update their color to the most frequent color in their neighborhood and a node keeps its color in case of a tie. We study the behavior of this basic process, which is called the majority model, on the Erdős–Rényi random graph Gn,p and regular expanders. First we consider the behavior of the majority model on Gn,p with an initial random configuration, where each node is blue independently with probability pb and red otherwise. It is shown that in this setting the process goes through a phase transition at the connectivity threshold, namely logn∕n. Furthermore, we say a graph G is λ-expander if the second-largest absolute eigenvalue of its adjacency matrix is λ. We prove that for a Δ-regular λ-expander graph if λ∕Δ is sufficiently small, then the majority model by starting from 1∕2−δn blue nodes (for an arbitrarily small constant δ>0) results in fully red configuration in sub-logarithmically many rounds. Roughly speaking, this means the majority model is an “efficient” and “fast” density classifier on regular expanders. As a by-product of our results, we show that regular Ramanujan graphs are asymptotically optimally immune, that is for an n-node Δ-regular Ramanujan graph if the initial number of blue nodes is s≤βn, the number of blue nodes in the next round is at most cs∕Δ for some constants c,β>0. © 2019 Elsevier B.V.
  • Protein folding in the HP model on grid lattices with diagonals
    Item type: Conference Paper
    Böckenhauer, Hans-Joachim; Bongartz, Dirk (2007)
    Discrete Applied Mathematics
  • Network flow interdiction on planar graphs
    Item type: Journal Article
    Zenklusen, R. (2010)
    Discrete Applied Mathematics
  • Path problems in generalized stars, complete graphs, and brick wall graphs
    Item type: Journal Article
    Erlebach, Thomas; Vukadinović, Danica (2006)
    Discrete Applied Mathematics
  • Traveling salesman games with the Monge property
    Item type: Journal Article
    Okamoto, Yoshio (2004)
    Discrete Applied Mathematics
  • Violator spaces
    Item type: Journal Article
    Gärtner, B.; Matoušek, Jiří; Rüst, L.; et al. (2008)
    Discrete Applied Mathematics
  • Simple Agents Learn to Find Their Way
    Item type: Journal Article
    Chalopin, Jérémie; Das, Shantanu; Disser, Yann; et al. (2013)
    Discrete Applied Mathematics
  • Efficient Minimization of Higher Order Submodular Functions using Monotonic Boolean Functions
    Item type: Journal Article
    Ramalingam, Srikumar; Russell, Chris; Ladický, Ľubor; et al. (2017)
    Discrete Applied Mathematics
  • Colorings of oriented planar graphs avoiding a monochromatic subgraph
    Item type: Journal Article
    Bergold, Helena; Hochstättler, Winfried; Steiner, Raphael (2022)
    Discrete Applied Mathematics
    For a fixed simple digraph F and a given simple digraph D, an F-free k-coloring of D is a vertex-coloring in which no induced copy of F in D is monochromatic. We study the complexity of deciding for fixed F and k whether a given simple digraph admits an F-free k-coloring. Our main focus is on the restriction of the problem to planar input digraphs, where it is only interesting to study the cases k ∈ {2, 3}. From known results it follows that for every fixed digraph F whose underlying graph is not a forest, every planar digraph D admits an F-free 2-coloring, and that for every fixed digraph F with ∆(F) ≥ 3, every oriented planar graph D admits an F-free 3-coloring. We show in contrast, that • if F is an orientation of a path of length at least 2, then it is NP-hard to decide whether an acyclic and planar input digraph D admits an F -free 2-coloring. • if F is an orientation of a path of length at least 1, then it is NP-hard to decide whether an acyclic and planar input digraph D admits an F-free 3-coloring.
Publications1 - 10 of 27