Outer independent rainbow dominating functions in graphs by Zhila Mansouri, Doost Ali Mojdeh

“…Finally, we show that any ordered pair \((a,b)\) is realizable as the vertex cover number and OI2-rD numbers of some non-trivial tree if and only if \(a+1\leq b\leq 2a\).…”
Get full text

Classifying and Benchmarking Quantum Annealing Algorithms Based on Quadratic Unconstrained Binary Optimization for Solving NP-Hard Problems by Jehn-Ruey Jiang, Chun-Wei Chu

“…It proposes a four-class classification of QUBO formulas and exemplifies each class by QUBO formulas used by QAAs for solving specific NP-hard problems, such as the subset sum, maximum cut, vertex cover, 0/1 knapsack, graph coloring, Hamiltonian cycle, traveling salesperson, and job shop scheduling problems. …”
Get full text

Applying Graph Neural Networks to the Decision Version of Graph Combinatorial Optimization Problems by Raka Jovanovic, Michael Palk, Sertac Bayhan, Stefan Voss

“…The selected problems are the minimum vertex cover, maximum clique, minimum dominating set and graph coloring. …”
Get full text

Discovering large conserved functional components in global network alignment by graph matching by Yuanyuan Zhu, Yuezhi Li, Juan Liu, Lu Qin, Jeffrey Xu Yu

“…It first selects some pairs of important proteins as seeds, followed by a gradual expansion to obtain an initial matching, and then it refines the current result to obtain an optimal alignment result iteratively based on the vertex cover. We compare GMAlign with the state-of-the-art methods on the PPI network pairs obtained from the largest BioGRID dataset and validate its performance. …”
Get full text

DIALIGN-TX: greedy and progressive approaches for segment-based multiple sequence alignment by Morgenstern Burkhard, Kaufmann Michael, Subramanian Amarendran R

“…The new method is based on a guide tree; to detect possible spurious sequence similarities, it employs a vertex-cover approximation on a conflict graph. We performed benchmarking tests on a large set of nucleic acid and protein sequences For protein benchmarks we used the benchmark database BALIBASE 3 and an updated release of the database IRMBASE 2 for assessing the quality on globally and locally related sequences, respectively. …”
Get full text

Risk-Aware Identification of Highly Suspected COVID-19 Cases in Social IoT: A Joint Graph Theory and Reinforcement Learning Approach by Bowen Wang, Yanjing Sun, Trung Q. Duong, Long D. Nguyen, Lajos Hanzo

“…By exploiting the so-called differential contact intensity and the infectious rate in susceptible-exposed-infected-removed (SEIR) epidemic model, the resultant optimization problem can be transformed into the minimum weight vertex cover (MWVC) problem of graph theory. To solve this problem in a high-dynamic random network topology, we propose an adaptive scheme by relying on the graph embedding technique during the state representation and reinforcement learning in the training phase. …”
Get full text

Incentive compatible design of reverse auctions. by Gravin, Nikolai.

“…We analyze the performance of incentive compatible procedures against two standard benchmarks and introduce a general scheme that proved to be optimal on some subclasses of vertex cover and all k-paths set systems. Our results completely settled the design of optimal frugal mechanism in path auctions, a decade-long standing open problem in algorithmic mechanism design proposed by Archer and Tardos. …”
Get full text

Graph Theoretical Analysis Reveals: Women's Brains Are Better Connected than Men's. by Balázs Szalkai, Bálint Varga, Vince Grolmusz

“…That size facilitates applying strict mathematical graph algorithms even for some hard-to-compute (or NP-hard) quantities like vertex cover or balanced minimum cut. In the present work we have examined brain graphs, computed from the data of the Human Connectome Project, recorded from male and female subjects between ages 22 and 35. …”
Get full text

Near Optimal Route Association With Shannon Model in Multi-Drone WSNs by Tao Wu, Panlong Yang, Yubo Yan, Ping Li, Xunpeng Rao

“…We prove the RSCA problem is NP-hard by reduction from the Vertex Cover problem and then devise an efficient and accessible O(log log n) approximation algorithm within the time complexity bound by O(p² log n log log n), where n is the number of sensor nodes and p is the number of routes in WSNs. …”
Get full text

Optimized Energy – Efficient Path Planning Strategy in WSN With Multiple Mobile Sinks by Bilal R. Al-Kaseem, Zahraa K. Taha, Sarah W. Abdulmajeed, Hamed S. Al-Raweshidy

“…A sojourn location determination algorithm is proposed based on the minimum weighted vertex cover problem (MWVCP) to find the best position for the sinks to stop and collect the data from cluster heads. …”
Get full text

Structural rounding: Approximation algorithms for graphs near an algorithmically tractable class by Demaine, Erik D, Liu, Quanquan C., Vakilian, Ali

“…We give a general characterization of when an optimization problem is amenable to this approach, and show that it includes many well-studied graph problems, such as INDEPENDENT SET, VERTEX COVER, FEEDBACK VERTEX SET, MINIMUM MAXIMAL MATCHING, CHROMATIC NUMBER, (ℓ-)DOMINATING SET, EDGE (ℓ-)DOMINATING SET, and CONNECTED DOMINATING SET. …”
Get full text

Local graph partitions for approximation and testing by Hassidim, Avinatan, Kelner, Jonathan Adam, Nguyen, Huy N., Onak, Krzysztof

“…We give constant-time approximation algorithms for the size of the minimum vertex cover, the minimum dominating set, and the maximum independent set for any class of graphs with an excluded minor.2. …”
Get full text
Get full text

An efficient partitioning oracle for bounded-treewidth graphs by Hassidim, Avinatan, Onak, Krzysztof, Edelman, Alan, Nguyen, Huy N.

“…Another application of the oracle is a poly(1/ε)-time algorithm that approximates the maximum matching size, the minimum vertex cover size, and the minimum dominating set size up to an additive εn in graphs with bounded treewidth. …”
Get full text
Get full text

Near-optimal distributed dominating set in bounded arboricity graphs by Dory, Michal, Ghaffari, Mohsen, Ilchi, Saeed

“…We also show a lower bound proving that this round complexity is nearly optimal even for the unweighted case, via a reduction from the celebrated KMW lower bound on distributed vertex cover approximation (Kuhn et al. in JACM 63:116, 2016). …”
Get full text

Approximation algorithms for packing and scheduling problems by Correa, José Rafael, 1975-

Get full text

Property testing : theory and applications by Raskhodnikova, Sofya, 1976-

Get full text

Approximation algorithms for combinatorial optimization under uncertainty by Minkoff, Maria, 1976-

Get full text

LP/SDP hierarchy lower bounds for decoding random LDPC codes by Ghazi, Badih

Get full text

Hardness magnification for natural problems by Santhanam, R, Oliveira, IC

“…If there is a c > 0 such that for each positive integer d there is an ε > 0 such that the problem of checking if an n-vertex graph in the adjacency matrix representation has a vertex cover of size (log n)^c cannot be solved by depth-d AC^0 circuits of size m^1+ε, where m = Θ(n^2), then NP does not have polynomial-size formulas. 3. …”

DynASP2.5: Dynamic Programming on Tree Decompositions in Action by Johannes K. Fichte, Markus Hecher, Michael Morak, Stefan Woltran

“…In the last few years, implementations for computing various parameters (parameter detection) have been established in parameterized challenges, such as treewidth, treedepth, hypertree width, feedback vertex set, or vertex cover. In theory, instances, for which the considered parameter is small, can be solved fast (problem evaluation), i.e., the runtime is bounded exponential in the parameter. …”
Get full text