Computing the largest bond and the maximum connected cut of a graph
From MaRDI portal
Publication:2663713
DOI10.1007/s00453-020-00789-1OpenAlexW3120331443MaRDI QIDQ2663713
Uéverton S. Souza, Yusuke Kobayashi, Rafael C. S. Schouery, Tesshu Hanaka, Hiroshi Eto, Daniel Lokshtanov, Yasuaki Kobayashi, Lehilton L. C. Pedrosa, Gabriel L. Duarte
Publication date: 19 April 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.04513
Related Items
On the minimum cycle cover problem on graphs with bounded co-degeneracy, On the bond polytope, Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the max min vertex cover problem
- On the reduction of Yutsis graphs
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- Clique-width of graphs defined by one-vertex extensions
- Graph structural properties of non-Yutsis graphs allowing fast recognition
- Graph minors. V. Excluding a planar graph
- Matching is as easy as matrix inversion
- A note on the approximation of a minimum-weight maximal independent set
- Maximum cut on line and total graphs
- On interval routing schemes and treewidth
- The many facets of upper domination
- A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs
- Approximating graph-constrained max-cut
- Feedback vertex set on graphs of low clique-width
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Approximation algorithms for connected maximum cut and related problems
- Weighted upper edge cover: complexity and approximability
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
- On some extremal problems in graph theory
- On maximum leaf trees and connections to connected maximum cut problems
- On the (co)girth of a connected matroid
- Large Wk- or K3,t-Minors in 3-Connected Graphs
- On the Maximum Weight Minimal Separator
- Multi-Terminal Network Flows
- Edge Dominating Sets in Graphs
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Maximum Minimal Vertex Cover Parameterized by Vertex Cover
- Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches
- Reducibility among Combinatorial Problems
- Parameterized Complexity of Multi-Node Hubs
- Imposing Connectivity Constraints in Forest Planning Models
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Approximation and intractability results for the maximum cut problem and its variants
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Probability and Computing
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- Computing the largest bond of a graph
