Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 18 of 18 for “"feedback vertex"”.

  1. A Branch and Cut Approach to the Feedback Vertex Set Problem

    … use a branch and cut implementation to solve the feedback vertex set problem and add new facet defining inequalities to the literature. Feedback in a system arises when repeated traversal over some cycle causes unwanted growth or decay in the data. This can cause problems in many systems such as …

    rice Repository record for A Branch and Cut Approach to the Feedback Vertex Set Problem (opens in a new tab)

  2. Randomized and Deterministic Parameterized Algorithms and Their Applications in Bioinformatics

    … problems, such as the p-path problem and the pd-feedback vertex set problem. Especially, we designed the first algorithm of running time in form of f(k)nO(1) for the pd-feedback vertex set problem. Thus solved an outstanding open problem, i.e. if the pd-feedback vertex set problem is FPT. …

    tamu Repository record for Randomized and Deterministic Parameterized Algorithms and Their Applications in Bioinformatics (opens in a new tab)

  3. Un Algoritmo Immunologico Ibrido per Estrarre Informazioni da Reti Complesse

    … Sono stati analizzati due problemi complessi: il Feedback Vertex Set sui grafi e il problema della Community Detection su reti complesse. Il Feedback Vertex Set è stato analizzato utilizzando un algoritmo immunologico ibrido, in cui l'esplorazione casuale dello spazio di ricerca è contenuta da …

    catania Repository record for Un Algoritmo Immunologico Ibrido per Estrarre Informazioni da Reti Complesse (opens in a new tab)

  4. Clustering and Inconsistent Information: A Kernelization Approach

    … vertices is the objective of the classical feedback vertex set (FVS) problem. This dissertation studies the three problems, correlation clustering, hierarchical clustering, and disjoint-FVS (a variation of FVS), from a kernelization approach. A kernelization algorithm in polynomial time …

    tamu Repository record for Clustering and Inconsistent Information: A Kernelization Approach (opens in a new tab)

  5. Directed Graphs: Fixed-Parameter Tractability & Beyond

    … problems such as Multiway Cut, Multicut, Subset Feedback Vertex Set, Odd Cycle Transversal, etc. was open. In the first part of the thesis, we develop the framework of <italic>shadowless solutions</italic> for a general class of transversal problems in directed graphs. For this class of problems, …

    maryland Repository record for Directed Graphs: Fixed-Parameter Tractability & Beyond (opens in a new tab)

  6. Transversal Problems In Sparse Graphs

    … behind the 18/7-approximation for ``uncrossable" feedback vertex set problems of Berman and Yaroslavtsev %% \cite{BermanY2012} noting that we do not need the larger ``witness" cycles to be a cycle that we need to hit. This we do in Chapter \ref{BermanYaroChapter}. In Chapter \ref{ErdosPosaChapter} …

    waterloo Repository record for Transversal Problems In Sparse Graphs (opens in a new tab)

  7. Irreversible k-threshold conversion processes on graphs

    … on G is an iterative process in which a white vertex becomes permanently coloured black at time t if at least k of its neighbours are coloured black at time t-1. A set S of vertices is an irreversible k-threshold conversion set (k-conversion set) of G if the initial colouring in which the …

    uvic Repository record for Irreversible k-threshold conversion processes on graphs (opens in a new tab)

  8. New approaches to integer programming

    … to give an approximation algorithm for the feedback vertex set problem (FVS) in a recently developed Implicit Hitting Set framework. Our algorithm is a simple online algorithm which finds a nearly optimal FVS in random graphs. We also propose a planted model for FVS and show that an optimal …

    gatech Repository record for New approaches to integer programming (opens in a new tab)

  9. Testability analysis and test generation for sequential VLSI circuits

    … all loops in a graph, commonly known as the feedback vertex problem is NP-complete. An algorithm based on heuristics is given to find small set of nodes that will break all loops. Design rules are given to reduce the test sequence length. Experimental results indicate the testability …

    nebraska Repository record for Testability analysis and test generation for sequential VLSI circuits (opens in a new tab)

  10. Measure-Driven Algorithm Design and Analysis: A New Approach for Solving NP-hard Problems

    … problems, the multiway cut problem, the feedback vertex set problems on both directed and undirected graph and the max-leaf problems on both directed and undirected graphs. Most of our algorithms are practical for problem instances with small parameters. Moreover, we show that this new …

    tamu Repository record for Measure-Driven Algorithm Design and Analysis: A New Approach for Solving NP-hard Problems (opens in a new tab)

  11. Exponential time algorithms via separators and random subsets

    … Φ (e.g., Φ could be the property of being a feedback vertex set for the input graph of size at most k). Our main tool is a simple randomized algorithm which solves Φ-Subset in time (1 + b − 1/c)^n N^O(1), provided that there is an algorithm for the Φ-Extension problem with b^{n−|X|}c^k N^O(1) …

    unsw Repository record for Exponential time algorithms via separators and random subsets (opens in a new tab)

  12. Path and cycle hitting problems: algorithms and complexity

    … thesis, we study terminal set problems: given a (vertex-weighted) graph and a vertex subset of the graph, called the terminal set, we search for a minimum-sized (minimum-weighted) vertex subset of the graph which intersects (hits) every vertex subset of the graph that contains a terminal and …

    greece Repository record for Path and cycle hitting problems: algorithms and complexity (opens in a new tab)

  13. On Reconfiguration Problems: Structure and Tractability

    Given an n-vertex graph G and two vertices s and t in G, determining whether there exists a path and computing the length of the shortest path between s and t are two of the most fundamental graph problems. In the classical battle of P versus NP or ``easy'' versus ``hard'', both of these problems …

    waterloo Repository record for On Reconfiguration Problems: Structure and Tractability (opens in a new tab)

  14. Algorithmic aspects of connectivity and density in graphs and hypergraphs

    Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms

    uiuc Repository record for Algorithmic aspects of connectivity and density in graphs and hypergraphs (opens in a new tab)