Relevant bibliographies by topics / Max-cut problems on graphs

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Max-cut problems on graphs'

Author: Grafiati
Published: 4 June 2021
Last updated: 1 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Max-cut problems on graphs.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Max-cut problems on graphs"

1

Bibak, Ali, Charles Carlson, and Karthekeyan Chandrasekaran. "Improving the Smoothed Complexity of FLIP for Max Cut Problems." ACM Transactions on Algorithms 17, no. 3 (2021): 1–38. http://dx.doi.org/10.1145/3454125.

Full text
Abstract:
Finding locally optimal solutions for MAX-CUT and MAX- k -CUT are well-known PLS-complete problems. An instinctive approach to finding such a locally optimum solution is the FLIP method. Even though FLIP requires exponential time in worst-case instances, it tends to terminate quickly in practical instances. To explain this discrepancy, the run-time of FLIP has been studied in the smoothed complexity framework. Etscheid and Röglin (ACM Transactions on Algorithms, 2017) showed that the smoothed complexity of FLIP for max-cut in arbitrary graphs is quasi-polynomial. Angel, Bubeck, Peres, and Wei (STOC, 2017) showed that the smoothed complexity of FLIP for max-cut in complete graphs is ( O Φ 5 n 15.1 ), where Φ is an upper bound on the random edge-weight density and Φ is the number of vertices in the input graph. While Angel, Bubeck, Peres, and Wei’s result showed the first polynomial smoothed complexity, they also conjectured that their run-time bound is far from optimal. In this work, we make substantial progress toward improving the run-time bound. We prove that the smoothed complexity of FLIP for max-cut in complete graphs is O (Φ n 7.83 ). Our results are based on a carefully chosen matrix whose rank captures the run-time of the method along with improved rank bounds for this matrix and an improved union bound based on this matrix. In addition, our techniques provide a general framework for analyzing FLIP in the smoothed framework. We illustrate this general framework by showing that the smoothed complexity of FLIP for MAX-3-CUT in complete graphs is polynomial and for MAX - k - CUT in arbitrary graphs is quasi-polynomial. We believe that our techniques should also be of interest toward showing smoothed polynomial complexity of FLIP for MAX - k - CUT in complete graphs for larger constants k .
APA, Harvard, Vancouver, ISO, and other styles
2

Bondarenko, Vladimir, and Andrei Nikolaev. "On Graphs of the Cone Decompositions for the Min-Cut and Max-Cut Problems." International Journal of Mathematics and Mathematical Sciences 2016 (2016): 1–6. http://dx.doi.org/10.1155/2016/7863650.

Full text
Abstract:
We consider maximum and minimum cut problems with nonnegative weights of edges. We define the graphs of the cone decompositions and find a linear clique number for the min-cut problem and a superpolynomial clique number for the max-cut problem. These values characterize the time complexity in a broad class of algorithms based on linear comparisons.
APA, Harvard, Vancouver, ISO, and other styles
3

Rodriguez-Fernandez, Angel E., Bernardo Gonzalez-Torres, Ricardo Menchaca-Mendez, and Peter F. Stadler. "Clustering Improves the Goemans–Williamson Approximation for the Max-Cut Problem." Computation 8, no. 3 (2020): 75. http://dx.doi.org/10.3390/computation8030075.

Full text
Abstract:
MAX-CUT is one of the well-studied NP-hard combinatorial optimization problems. It can be formulated as an Integer Quadratic Programming problem and admits a simple relaxation obtained by replacing the integer “spin” variables xi by unitary vectors v→i. The Goemans–Williamson rounding algorithm assigns the solution vectors of the relaxed quadratic program to a corresponding integer spin depending on the sign of the scalar product v→i·r→ with a random vector r→. Here, we investigate whether better graph cuts can be obtained by instead using a more sophisticated clustering algorithm. We answer this question affirmatively. Different initializations of k-means and k-medoids clustering produce better cuts for the graph instances of the most well known benchmark for MAX-CUT. In particular, we found a strong correlation of cluster quality and cut weights during the evolution of the clustering algorithms. Finally, since in general the maximal cut weight of a graph is not known beforehand, we derived instance-specific lower bounds for the approximation ratio, which give information of how close a solution is to the global optima for a particular instance. For the graphs in our benchmark, the instance specific lower bounds significantly exceed the Goemans–Williamson guarantee.
APA, Harvard, Vancouver, ISO, and other styles
4

Hamerly, Ryan, Takahiro Inagaki, Peter L. McMahon, et al. "Experimental investigation of performance differences between coherent Ising machines and a quantum annealer." Science Advances 5, no. 5 (2019): eaau0823. http://dx.doi.org/10.1126/sciadv.aau0823.

Full text
Abstract:
Physical annealing systems provide heuristic approaches to solving combinatorial optimization problems. Here, we benchmark two types of annealing machines—a quantum annealer built by D-Wave Systems and measurement-feedback coherent Ising machines (CIMs) based on optical parametric oscillators—on two problem classes, the Sherrington-Kirkpatrick (SK) model and MAX-CUT. The D-Wave quantum annealer outperforms the CIMs on MAX-CUT on cubic graphs. On denser problems, however, we observe an exponential penalty for the quantum annealer [exp(–αDWN2)] relative to CIMs [exp(–αCIMN)] for fixed anneal times, both on the SK model and on 50% edge density MAX-CUT. This leads to a several orders of magnitude time-to-solution difference for instances with over 50 vertices. An optimal–annealing time analysis is also consistent with a substantial projected performance difference. The difference in performance between the sparsely connected D-Wave machine and the fully-connected CIMs provides strong experimental support for efforts to increase the connectivity of quantum annealers.
APA, Harvard, Vancouver, ISO, and other styles
5

Zivan, Roie, Omer Lev, and Rotem Galiki. "Beyond Trees: Analysis and Convergence of Belief Propagation in Graphs with Multiple Cycles." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 05 (2020): 7333–40. http://dx.doi.org/10.1609/aaai.v34i05.6227.

Full text
Abstract:
Belief propagation, an algorithm for solving problems represented by graphical models, has long been known to converge to the optimal solution when the graph is a tree. When the graph representing the problem includes a single cycle, the algorithm either converges to the optimal solution or performs periodic oscillations. While the conditions that trigger these two behaviors have been established, the question regarding the convergence and divergence of the algorithm on graphs that include more than one cycle is still open.Focusing on Max-sum, the version of belief propagation for solving distributed constraint optimization problems (DCOPs), we extend the theory on the behavior of belief propagation in general – and Max-sum specifically – when solving problems represented by graphs with multiple cycles. This includes: 1) Generalizing the results obtained for graphs with a single cycle to graphs with multiple cycles, by using backtrack cost trees (BCT). 2) Proving that when the algorithm is applied to adjacent symmetric cycles, the use of a large enough damping factor guarantees convergence to the optimal solution.
APA, Harvard, Vancouver, ISO, and other styles
6

COUDERT, D., P. DATTA, S. PERENNES, H. RIVANO, and M. E. VOGE. "SHARED RISK RESOURCE GROUP COMPLEXITY AND APPROXIMABILITY ISSUES." Parallel Processing Letters 17, no. 02 (2007): 169–84. http://dx.doi.org/10.1142/s0129626407002958.

Full text
Abstract:
This article investigates complexity and approximability properties of combinatorial optimization problems yielded by the notion of Shared Risk Resource Group (SRRG). SRRG has been introduced in order to capture network survivability issues where a failure may break a whole set of resources, and has been formalized as colored graphs, where a set of resources is represented by a set of edges with same color. We consider here the analogous of classical problems such as determining paths or cuts with the minimum numbers of colors or color disjoint paths. These optimization problems are much more difficult than their counterparts in classical graph theory. In particular standard relationship such as the Max Flow - Min Cut equality do not hold any longer. In this article we identify cases where these problems are polynomial, for example when the edges of a given color form a connected subgraph, and otherwise give hardness and non approximability results for these problems.
APA, Harvard, Vancouver, ISO, and other styles
7

Wu, Y., P. Austrin, T. Pitassi, and D. Liu. "Inapproximability of Treewidth and Related Problems." Journal of Artificial Intelligence Research 49 (April 6, 2014): 569–600. http://dx.doi.org/10.1613/jair.4030.

Full text
Abstract:
Graphical models, such as Bayesian Networks and Markov networks play an important role in artificial intelligence and machine learning. Inference is a central problem to be solved on these networks. This, and other problems on these graph models are often known to be hard to solve in general, but tractable on graphs with bounded Treewidth. Therefore, finding or approximating the Treewidth of a graph is a fundamental problem related to inference in graphical models. In this paper, we study the approximability of a number of graph problems: Treewidth and Pathwidth of graphs, Minimum Fill-In, One-Shot Black (and Black-White) pebbling costs of directed acyclic graphs, and a variety of different graph layout problems such as Minimum Cut Linear Arrangement and Interval Graph Completion. We show that, assuming the recently introduced Small Set Expansion Conjecture, all of these problems are NP-hard to approximate to within any constant factor in polynomial time.
APA, Harvard, Vancouver, ISO, and other styles
8

Koam, Ali N. A., Muhammad Akram, and Peide Liu. "Decision-Making Analysis Based on Fuzzy Graph Structures." Mathematical Problems in Engineering 2020 (August 12, 2020): 1–30. http://dx.doi.org/10.1155/2020/6846257.

Full text
Abstract:
A graph structure is a useful framework to solve the combinatorial problems in various fields of computational intelligence systems and computer science. In this research article, the concept of fuzzy sets is applied to the graph structure to define certain notions of fuzzy graph structures. Fuzzy graph structures can be very useful in the study of various structures, including fuzzy graphs, signed graphs, and the graphs having labeled or colored edges. The notions of the fuzzy graph structure, lexicographic-max product, and degree and total degree of a vertex in the lexicographic-max product are introduced. Further, the proposed concepts are explained through several numerical examples. In particular, applications of the fuzzy graph structures in decision-making process, regarding detection of marine crimes and detection of the road crimes, are presented. Finally, the general procedure of these applications is described by an algorithm.
APA, Harvard, Vancouver, ISO, and other styles
9

Drineas, Petros, Ravi Kannan, and Michael W. Mahoney. "Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms." Random Structures & Algorithms 32, no. 3 (2007): 307–33. http://dx.doi.org/10.1002/rsa.20196.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Engelberg, Roee, Jochen Könemann, Stefano Leonardi, and Joseph (Seffi) Naor. "Cut problems in graphs with a budget constraint." Journal of Discrete Algorithms 5, no. 2 (2007): 262–79. http://dx.doi.org/10.1016/j.jda.2006.05.002.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Max-cut problems on graphs"

1

Levine, Matthew S. (Matthew Steven). "Algorithms for connectivity problems in undirected graphs : maximum flow and minimun [kappa]-way cut." Thesis, Massachusetts Institute of Technology, 2002. http://hdl.handle.net/1721.1/29234.

Full text
Abstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002.<br>In title on t.p., "[kappa]" apears as lower-case Greek letter.<br>Includes bibliographical references (p. [69]-72).<br>We consider two connectivity problems on undirected graphs: maximum flow and minimum k-way cut. The maximum flow problem asks about the connectivity between two specified nodes. A traditional approach is to search for augmenting paths. We explore the possibility of restricting the set of edges in which we search for an augmenting path, so that we can find each flow path in sub-linear time. Consider an n-vertex, m-edge, undirected graph with maximum flow value v. We give two methods for finding augmenting paths in such a graph in amortized sub-linear time, based on the idea that undirected graphs have sparse subgraphs that capture connectivity information. The first method sparsifies unused edges by using a spanning forest. It is deterministic and takes ... time per path on average. The second method sparsifies the entire residual graph by taking random samples of the edges. It takes O(n) time per path on average. These results let us improve the O(mv) time bound of the classic augmenting path algorithm to O(m + nv3/2) (deterministic) and O(m + nv) (randomized). For simple graphs, the addition of a blocking flow subroutine yields a deterministic O (nm2/3vl/6)-time algorithm. A minimum k-way cut of an n-vertex, m-edge, weighted, undirected graph is a partition of the vertices into k sets that minimizes the total weight of edges with endpoints in different sets. We give new randomized algorithms to find minimum 3-way and 4-way cuts, which lead to time bounds of O(mnk-2 log3 n) for k =/< 6. Our key insight is that two different structural properties of k-way cuts, both exploited by previous algorithms, can be exploited simultaneously to avoid the bottleneck operations in both prior algorithms. The result is that we improve on the best previous time bounds by a factor of O(n2).<br>Ph.D.
APA, Harvard, Vancouver, ISO, and other styles
2

Fukuda, Ellen Hidemi. "Algoritmo do volume e otimização não diferenciável." Universidade de São Paulo, 2007. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04062007-115956/.

Full text
Abstract:
Uma maneira de resolver problemas de programação linear de grande escala é explorar a relaxação lagrangeana das restrições \"difíceis\'\' e utilizar métodos de subgradientes. Populares por fornecerem rapidamente boas aproximações de soluções duais, eles não produzem diretamente as soluções primais. Para obtê-las com custo computacional adequado, pode-se construir seqüências ergódicas ou utilizar uma técnica proposta recentemente, denominada algoritmo do volume. As propriedades teóricas de convergência não foram bem estabelecidas nesse algoritmo, mas pequenas modificações permitem a demonstração da convergência dual. Destacam-se como adaptações o algoritmo do volume revisado, um método de feixes específico, e o algoritmo do volume incorporado ao método de variação do alvo. Este trabalho foi baseado no estudo desses algoritmos e de todos os conceitos envolvidos, em especial, análise convexa e otimização não diferenciável. Estudamos as principais diferenças teóricas desses métodos e realizamos comparações numéricas com problemas lineares e lineares inteiros, em particular, o corte máximo em grafos.<br>One way to solve large-scale linear programming problems is to exploit the Lagrangian relaxation of the difficult constraints and use subgradient methods. Such methods are popular as they give good approximations of dual solutions. Unfortunately, they do not directly yield primal solutions. Two alternatives to obtain primal solutions under reasonable computational cost are the construction of ergodic sequences and the use of the recently developed volume algorithm. While the convergence of ergodic sequences is well understood, the convergence properties of the volume algorithm is not well established in the original paper. This lead to some modifications of the original method to ease the proof of dual convergence. Three alternatives are the revised volume algorithm, a special case of the bundle method, and the volume algorithm incorporated by the variable target value method. The aim of this work is to study such algorithms and all related concepts, especially convex analysis and nondifferentiable optimization. We analysed the main theoretical differences among the methods and performed numerical experiments with linear and integer problems, in particular, the maximum cut problem on graphs.
APA, Harvard, Vancouver, ISO, and other styles
3

Zou, Mengchuan. "Aspects of efficiency in selected problems of computation on large graphs." Thesis, Université de Paris (2019-....), 2019. http://www.theses.fr/2019UNIP7132.

Full text
Abstract:
Cette thèse présente trois travaux liés à la conception d’algorithmes efficaces applicables à des graphes de grande taille. Dans le premier travail, nous nous plaçons dans le cadre du calcul centralisé, et ainsi la question de la généralisation des décompositions modulaires et de la conception d’un algorithme efficace pour ce problème. La décomposition modulaire et la détection de module, sont des moyens de révéler et d’analyser les propriétés modulaires de données structurées. Comme la décomposition modulaire classique est bien étudiée et possède un algorithme de temps linéaire optimal, nous étudions d’abord les généralisations de ces concepts en hypergraphes. C’est un sujet peu étudié mais qui permet de trouver de nouvelles structurations dans les familles de parties. Nous présentons ici des résultats positifs obtenus pour trois définitions de la décomposition modulaire dans les hypergraphes de la littérature. Nous considérons également la généralisation en permettant des erreurs dans les modules de graphes classiques et présentons des résultats négatifs pour deux telles définitions. Le deuxième travail est sur des requêtes de données dans un graphe. Ici, le modèle diffère des scénarios classiques dans le sens que nous ne concevons pas d’algorithmes pour résoudre un problème original, mais nous supposons qu’il existe un oracle fournissant des informations partielles sur la solution de problème initial, où les oracle ont une consommation de temps ou de ressources de requête que nous modélisons en tant que coûts, et nous avons besoin d’un algorithme décidant comment interroger efficacement l’oracle pour obtenir la solution exacte au problème initial. L’efficacité ici concerne le coût de la requête. Nous étudions un problème de la méthode de dichotomie généralisée pour lequel nous calculons une stratégie d’interrogation efficace afin de trouver une cible cachée dans le graphe. Nous présentons les résultats de nos travaux sur l’approximation de la stratégie optimale de recherche en dichotomie généralisée sur les arbres pondérés. Notre troisième travail est sur la question de l’efficacité de la mémoire. La configuration dans laquelle nous étudions sont des calculs distribués et avec la limitation en mémoire. Plus précisément, chaque nœud stocke ses données locales en échangeant des données par transmission de messages et est en mesure de procéder à des calculs locaux. Ceci est similaire au modèle LOCAL / CONGEST en calcul distribué, mais notre modèle requiert en outre que chaque nœud ne puisse stocker qu’un nombre constant de variables w.r.t. son degré. Ce modèle peut également décrire des algorithmes naturels. Nous implémentons une procédure existante de repondération multiplicative pour approximer le problème de flux maximal sur ce modèle. D’un point de vue méthodologique, les trois types d’efficacité que nous avons étudiées correspondent aux trois types de scénarios suivants: – Le premier est le plus classique. Considérant un problème, nous essayons de concevoir à la main l’algorithme le plus efficace. – Dans le second, l’efficacité est considérée comme un objectif. Nous modélisons les coûts de requête comme une fonction objectif, et utilisons des techniques d’algorithme d’approximation pour obtenir la conception d’une stratégie efficace. – Dans le troisième, l’efficacité est en fait posée comme une contrainte de mémoire et nous concevons un algorithme sous cette contrainte<br>This thesis presents three works on different aspects of efficiency of algorithm design for large scale graph computations. In the first work, we consider a setting of classical centralized computing, and we consider the question of generalizing modular decompositions and designing time efficient algorithm for this problem. Modular decomposition, and more broadly module detection, are ways to reveal and analyze modular properties in structured data. As the classical modular decomposition is well studied and have an optimal linear time algorithm, we firstly study the generalizations of these concepts to hypergraphs and present here positive results obtained for three definitions of modular decomposition in hypergraphs from the literature. We also consider the generalization of allowing errors in classical graph modules and present negative results for two this kind of definitions. The second work focuses on graph data query scenarios. Here the model differs from classical computing scenarios in that we are not designing algorithms to solve an original problem, but we assume that there is an oracle which provides partial information about the solution to the original problem, where oracle queries have time or resource consumption, which we model as costs, and we need to have an algorithm deciding how to efficiently query the oracle to get the exact solution to the original problem, thus here the efficiency is addressing to the query costs. We study the generalized binary search problem for which we compute an efficient query strategy to find a hidden target in graphs. We present the results of our work on approximating the optimal strategy of generalized binary search on weighted trees. Our third work draws attention to the question of memory efficiency. The setup in which we perform our computations is distributed and memory restricted. Specifically, every node stores its local data, exchanging data by message passing, and is able to proceed local computations. This is similar to the LOCAL/CONGEST model in distributed computing, but our model additionally requires that every node can only store a constant number of variables w.r.t. its degree. This model can also describe natural algorithms. We implement an existing procedure of multiplicative reweighting for approximating the maximum s–t flow problem on this model, this type of methodology may potentially provide new opportunities for the field of local or natural algorithms. From a methodological point of view, the three types of efficiency concerns correspond to the following types of scenarios: the first one is the most classical one given the problem, we try to design by hand the more efficient algorithm; the second one, the efficiency is regarded as an objective function .where we model query costs as an objective function, and using approximation algorithm techniques to get a good design of efficient strategy; the third one, the efficiency is in fact posed as a constraint of memory and we design algorithm under this constraint
APA, Harvard, Vancouver, ISO, and other styles
4

Florén, Mikael. "Approximation of Max-Cut on Graphs of Bounded Degree." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-189143.

Full text
Abstract:
The Max-Cut problem is a well-known NP-hard problem, for which numerous approximation algorithms have been developed over the years. In this thesis, we examine the special case where the degree of vertices in the graph is bounded. With minor modifications to existing algorithms, we are able to obtain an improved approximation ratio for general bounded-degree graphs. Furthermore we show additional improvements for graphs with at least a constant fraction of odd-degree vertices. We also identify some other possible areas for improvement in the general bounded-degree case.<br>Max-Cut-problemet är ett välkänt NP-svårt problem, för vilket ett flertal olika approximationsalgoritmer har utvecklats över åren. I det här arbetet undersöks specialfallet då grafens noder har begränsat gradtal. Med mindre förändringar av existerande algoritmer lyckas vi uppnå en förbättrad approximationskvot för generella gradtals-begränsade grafer. Vi visar också ytterligare förbättringar för grafer med minst en konstant andel noder med udda gradtal. Vi identifierar också några andra möjliga områden för förbättring i det allmänna gradtals-begränsade fallet.
APA, Harvard, Vancouver, ISO, and other styles
5

Le, Bodic Pierre. "Variantes non standards de problèmes d'optimisation combinatoire." Thesis, Paris 11, 2012. http://www.theses.fr/2012PA112190.

Full text
Abstract:
Cette thèse est composée de deux parties, chacune portant sur un sous-domaine de l'optimisation combinatoire a priori distant de l'autre. Le premier thème de recherche abordé est la programmation biniveau stochastique. Se cachent derrière ce terme deux sujets de recherche relativement peu étudiés conjointement, à savoir d'un côté la programmation stochastique, et de l'autre la programmation biniveau. La programmation mathématique (PM) regroupe un ensemble de méthodes de modélisation et de résolution, pouvant être utilisées pour traiter des problèmes pratiques que se posent des décideurs. La programmation stochastique et la programmation biniveau sont deux sous-domaines de la PM, permettant chacun de modéliser un aspect particulier de ces problèmes pratiques. Nous élaborons un modèle mathématique issu d'un problème appliqué, où les aspects biniveau et stochastique sont tous deux sollicités, puis procédons à une série de transformations du modèle. Une méthode de résolution est proposée pour le PM résultant. Nous démontrons alors théoriquement et vérifions expérimentalement la convergence de cette méthode. Cet algorithme peut être utilisé pour résoudre d'autres programmes biniveaux que celui qui est proposé.Le second thème de recherche de cette thèse s'intitule "problèmes de coupe et de couverture partielles dans les graphes". Les problèmes de coupe et de couverture sont parmi les problèmes de graphe les plus étudiés du point de vue complexité et algorithmique. Nous considérons certains de ces problèmes dans une variante partielle, c'est-à-dire que la propriété de coupe ou de couverture dont il est question doit être vérifiée partiellement, selon un paramètre donné, et non plus complètement comme c'est le cas pour les problèmes originels. Précisément, les problèmes étudiés sont le problème de multicoupe partielle, de coupe multiterminale partielle, et de l'ensemble dominant partiel. Les versions sommets des ces problèmes sont également considérés. Notons que les problèmes en variante partielle généralisent les problèmes non partiels. Nous donnons des algorithmes exacts lorsque cela est possible, prouvons la NP-difficulté de certaines variantes, et fournissons des algorithmes approchés dans des cas assez généraux<br>This thesis is composed of two parts, each part belonging to a sub-domain of combinatorial optimization a priori distant from the other. The first research subject is stochastic bilevel programming. This term regroups two research subject rarely studied together, namely stochastic programming on the one hand, and bilevel programming on the other hand. Mathematical Programming (MP) is a set of modelisation and resolution methods, that can be used to tackle practical problems and help take decisions. Stochastic programming and bilevel programming are two sub-domains of MP, each one of them being able to model a specific aspect of these practical problems. Starting from a practical problem, we design a mathematical model where the bilevel and stochastic aspects are used together, then apply a series of transformations to this model. A resolution method is proposed for the resulting MP. We then theoretically prove and numerically verify that this method converges. This algorithm can be used to solve other bilevel programs than the ones we study.The second research subject in this thesis is called "partial cut and cover problems in graphs". Cut and cover problems are among the most studied from the complexity and algorithmical point of view. We consider some of these problems in a partial variant, which means that the cut or cover property that is looked into must be verified partially, according to a given parameter, and not completely, as it was the case with the original problems. More precisely, the problems that we study are the partial multicut, the partial multiterminal cut, and the partial dominating set. Versions of these problems were vertices are
APA, Harvard, Vancouver, ISO, and other styles
6

Hirschfeld, Bernd. "Approximative Lösungen des Max-cut-Problems mit semidefiniten Programmen." [S.l. : s.n.], 2004. http://deposit.ddb.de/cgi-bin/dokserv?idn=970150032.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Curado, Manuel. "Structural Similarity: Applications to Object Recognition and Clustering." Doctoral thesis, Universidad de Alicante, 2018. http://hdl.handle.net/10045/98110.

Full text
Abstract:
In this thesis, we propose many developments in the context of Structural Similarity. We address both node (local) similarity and graph (global) similarity. Concerning node similarity, we focus on improving the diffusive process leading to compute this similarity (e.g. Commute Times) by means of modifying or rewiring the structure of the graph (Graph Densification), although some advances in Laplacian-based ranking are also included in this document. Graph Densification is a particular case of what we call graph rewiring, i.e. a novel field (similar to image processing) where input graphs are rewired to be better conditioned for the subsequent pattern recognition tasks (e.g. clustering). In the thesis, we contribute with an scalable an effective method driven by Dirichlet processes. We propose both a completely unsupervised and a semi-supervised approach for Dirichlet densification. We also contribute with new random walkers (Return Random Walks) that are useful structural filters as well as asymmetry detectors in directed brain networks used to make early predictions of Alzheimer's disease (AD). Graph similarity is addressed by means of designing structural information channels as a means of measuring the Mutual Information between graphs. To this end, we first embed the graphs by means of Commute Times. Commute times embeddings have good properties for Delaunay triangulations (the typical representation for Graph Matching in computer vision). This means that these embeddings can act as encoders in the channel as well as decoders (since they are invertible). Consequently, structural noise can be modelled by the deformation introduced in one of the manifolds to fit the other one. This methodology leads to a very high discriminative similarity measure, since the Mutual Information is measured on the manifolds (vectorial domain) through copulas and bypass entropy estimators. This is consistent with the methodology of decoupling the measurement of graph similarity in two steps: a) linearizing the Quadratic Assignment Problem (QAP) by means of the embedding trick, and b) measuring similarity in vector spaces. The QAP problem is also investigated in this thesis. More precisely, we analyze the behaviour of $m$-best Graph Matching methods. These methods usually start by a couple of best solutions and then expand locally the search space by excluding previous clamped variables. The next variable to clamp is usually selected randomly, but we show that this reduces the performance when structural noise arises (outliers). Alternatively, we propose several heuristics for spanning the search space and evaluate all of them, showing that they are usually better than random selection. These heuristics are particularly interesting because they exploit the structure of the affinity matrix. Efficiency is improved as well. Concerning the application domains explored in this thesis we focus on object recognition (graph similarity), clustering (rewiring), compression/decompression of graphs (links with Extremal Graph Theory), 3D shape simplification (sparsification) and early prediction of AD.<br>Ministerio de Economía, Industria y Competitividad (Referencia TIN2012-32839 BES-2013-064482)
APA, Harvard, Vancouver, ISO, and other styles
8

Fügenschuh, Marzena. "Relaxations and solutions for the minimum graph bisection problem /." Berlin : Logos-Verl, 2007. http://deposit.d-nb.de/cgi-bin/dokserv?id=3025314&prov=M&dok_var=1&dok_ext=htm.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Calinescu, Gruia. "Approximation algorithms for graph-theoretic problems : planar subgraphs and multiway cut." Diss., Georgia Institute of Technology, 1998. http://hdl.handle.net/1853/9203.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Hartmann, Tanja [Verfasser], and D. [Akademischer Betreuer] Wagner. "Algorithms for Graph Connectivity and Cut Problems - Connectivity Augmentation, All-Pairs Minimum Cut, and Cut-Based Clustering / Tanja Hartmann. Betreuer: D. Wagner." Karlsruhe : KIT-Bibliothek, 2014. http://d-nb.info/1064504167/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Max-cut problems on graphs"

1

Lau, Lap Chi. On approximate min-max theorems for graph connectivity problems. 2006.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Newman, Mark. Mathematics of networks. Oxford University Press, 2018. http://dx.doi.org/10.1093/oso/9780198805090.003.0006.

Full text
Abstract:
An introduction to the mathematical tools used in the study of networks. Topics discussed include: the adjacency matrix; weighted, directed, acyclic, and bipartite networks; multilayer and dynamic networks; trees; planar networks. Some basic properties of networks are then discussed, including degrees, density and sparsity, paths on networks, component structure, and connectivity and cut sets. The final part of the chapter focuses on the graph Laplacian and its applications to network visualization, graph partitioning, the theory of random walks, and other problems.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Max-cut problems on graphs"

1

Calamoneri, T., I. Finocchi, R. Petreschi, and Y. Manoussakis. "A Parallel Approximation Algorithm for the Max Cut Problem on Cubic Graphs." In Advances in Computing Science — ASIAN’99. Springer Berlin Heidelberg, 1999. http://dx.doi.org/10.1007/3-540-46674-6_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Engelberg, Roee, Jochen Könemann, Stefano Leonardi, and Joseph Naor. "Cut Problems in Graphs with a Budget Constraint." In LATIN 2006: Theoretical Informatics. Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11682462_41.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Baïou, Mourad, and Francisco Barahona. "Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem." In Integer Programming and Combinatorial Optimization. Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-33461-5_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Dahn, Christine, Nils M. Kriege, and Petra Mutzel. "A Fixed-Parameter Algorithm for the Max-Cut Problem on Embedded 1-Planar Graphs." In Lecture Notes in Computer Science. Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-94667-2_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Matusiewicz, Zofia, and Krzysztof Pancerz. "Rough Set Flow Graphs and Max − * Fuzzy Relation Equations in State Prediction Problems." In Rough Sets and Current Trends in Computing. Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-88425-5_37.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

de Sousa, Samuel, Yll Haxhimusa, and Walter G. Kropatsch. "Estimation of Distribution Algorithm for the Max-Cut Problem." In Graph-Based Representations in Pattern Recognition. Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-38221-5_26.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Angel, Eric, Evripidis Bampis, and Laurent Gourvès. "Approximation Algorithms for the Bi-criteria Weighted max-cut Problem." In Graph-Theoretic Concepts in Computer Science. Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11604686_29.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Kamiński, Marcin. "max-cut and Containment Relations in Graphs." In Graph Theoretic Concepts in Computer Science. Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-16926-7_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Sharifov, Firdovsi, and Hakan Kutucu. "Network Design Problem with Cut Constraints." In Optimization Problems in Graph Theory. Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-94830-0_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Watrigant, R., M. Bougeret, R. Giroudeau, and J. C. König. "Sum-Max Graph Partitioning Problem." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-32147-4_27.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Max-cut problems on graphs"

1

Chuzhoy, Julia, and Sanjeev Khanna. "Hardness of cut problems in directed graphs." In the thirty-eighth annual ACM symposium. ACM Press, 2006. http://dx.doi.org/10.1145/1132516.1132593.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Madry, Aleksander. "Fast Approximation Algorithms for Cut-Based Problems in Undirected Graphs." In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2010. http://dx.doi.org/10.1109/focs.2010.30.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Assadi, Sepehr, Gillat Kol, Raghuvansh R. Saxena, and Huacheng Yu. "Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems." In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2020. http://dx.doi.org/10.1109/focs46700.2020.00041.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Da Silva, Thiago Gouveia. "The Minimum Labeling Spanning Tree and Related Problems." In XXXII Concurso de Teses e Dissertações da SBC. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/ctd.2019.6333.

Full text
Abstract:
The minimum labeling spanning tree problem (MLSTP) is a combinatorial optimization problem that consists in finding a spanning tree in a simple edge-labeled graph, i.e., a graph in which each edge has one label associated, by using a minimum number of labels. It is an NP-hard problem that has attracted substantial research attention in recent years. In its turn, the generalized minimum labeling spanning tree problem (GMLSTP) is a generalization of the MLSTP that allows the situation in which multiple labels can be assigned to an edge. Both problems have several practical applications in important areas such as computer network design, multimodal transportation network design, and data compression. The thesis addresses several connectivity problems defined over edge-labeled graphs, in special the minimum labeling spanning tree problem and its generalized version. The contributions in the work can be classified between theoretical and practical. On the theoretical side, it has introduced new useful concepts, definitions, properties and theorems regarding edge-labeled graphs, as well as a polyhedral study on the GMLSTP. On the practical side, we have proposed new heuristics and new mathematical formulations and branch-and-cut algorithms. The new approaches introduced have achieved the best results for both heuristic and exact methods in comparison with the state-of-the-art.
APA, Harvard, Vancouver, ISO, and other styles
5

Monteiro, Bruno, and Vinicius Dos Santos. "Equitable Partition of Graphs into Independent Sets and Cliques." In IV Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/etc.2019.6392.

Full text
Abstract:
A graph is (k, l) if its vertex set can be partitioned into k independent sets and l cliques. Deciding if a graph is (k, l) can be seen as a generalization of coloring, since deciding is a graph belongs to (k, 0) corresponds to deciding if a graph is k-colorable. A coloring is equitable if the cardinalities of the color classes differ by at most 1. In this paper, we generalize both the (k, l) and the equitable coloring problems, by showing that deciding whether a given graph can be equitably partitioned into k independent sets and l cliques is solvable in polynomial time if max(k, l) 2, and NP complete otherwise.
APA, Harvard, Vancouver, ISO, and other styles
6

Daudé, Hervé, Conrado Martínez, Vonjy Rasendrahasina, and Vlady Ravelomanana. "The MAX-CUT of sparse random graphs." In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2012. http://dx.doi.org/10.1137/1.9781611973099.24.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Italiano, Giuseppe F., Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. "Improved algorithms for min cut and max flow in undirected planar graphs." In the 43rd annual ACM symposium. ACM Press, 2011. http://dx.doi.org/10.1145/1993636.1993679.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Mansilla, Lucy A. C., and Paulo A. V. Miranda. "Object segmentation by Oriented Image Foresting Transform with connectivity constraints." In XXXII Conference on Graphics, Patterns and Images. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/sibgrapi.est.2019.8305.

Full text
Abstract:
Global properties, such as connectivity, shape constraints and boundary polarity, are useful high-level priors for image segmentation, allowing its customization for a given target object. In this work, we introduce a new method called Connected Oriented Image Foresting Transform (COIFT), which provides global optimum solutions according to a graph-cut measure, subject to the connectivity constraint in Oriented Image Foresting Transform (OIFT), ensuring the generation of connected objects, as well as allowing the simultaneous control of the boundary polarity. While the use of connectivity constraints in other frameworks, such as in the min-cut/max-flow algorithm, leads to an NP-Hard problem, COIFT conserves the low complexity of the OIFT algorithm. Experiments show that COIFT can considerably improve the segmentation of objects with thin and elongated parts, for the same number of seeds in segmentation based on markers.
APA, Harvard, Vancouver, ISO, and other styles
9

Carr, Peter, and Richard Hartley. "Solving Multilabel Graph Cut Problems with Multilabel Swap." In 2009 Digital Image Computing: Techniques and Applications. IEEE, 2009. http://dx.doi.org/10.1109/dicta.2009.90.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Tuysuzoglu, Ahmet, Ivana Stojanovic, David Castanon, and W. Clem Karl. "A graph cut method for linear inverse problems." In 2011 18th IEEE International Conference on Image Processing (ICIP 2011). IEEE, 2011. http://dx.doi.org/10.1109/icip.2011.6115844.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Max-cut problems on graphs"

1

Leighton, Tom, and Satish Rao. An Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms. Defense Technical Information Center, 1989. http://dx.doi.org/10.21236/ada211908.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Max-cut problems on graphs' for particular source types:
Journal articles Dissertations / Theses
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography