All Questions
30 questions
5
votes
1
answer
291
views
Minimum number of edges to remove to have low degree
I have the following problem, where $k$ is a fixed integer.
Input: Graph $G$.
Output: Minimum number of edges to remove from $G$ to obtain a graph such that every node has degree at most $k$.
Do ...
- 613
4
votes
2
answers
315
views
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
- 269
4
votes
1
answer
1k
views
Algorithm for the shortest path through all the points of a 2D cloud
I have an array of points with their coordinates X and Y. Each point represents a bus stop.
I need to sort the points in a sequence by giving them sequence numbers, so that the path from the first to ...
- 61
4
votes
0
answers
175
views
What is known about the complexity of this covering problem?
Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
- 2,966
3
votes
2
answers
336
views
Algorithm to evaluate "connectedness" of a binary matrix
I have the following problem: given an $m \times n$ binary matrix $A$ like e.g. the following $9 \times 39$ matrix:
...
- 1,000
3
votes
1
answer
305
views
Counting the forests obtainable by removing subtrees from binary trees
Let $B_h$ be the perfect binary tree having height $h$ (i.e. the binary tree with height $h$ in which all interior nodes have two children and all leaves have the same depth or same level).
For any ...
- 1,677
3
votes
1
answer
154
views
A modified bipartite assignment problem
Consider the following optimization problem. I have $n$ advisors and $dn$ students. I want to assign each student an advisor so that each advisor has exactly $d$ students. Each advisor/student pair ...
- 1,500
3
votes
1
answer
240
views
Algorithm for finding a minimum weight circuit in a weighted binary matroid
For a given weighted graph $G = (V, E)$, there is a simple algorithm for finding the minimum weight circuit by running Dijkstra's algorithm $|E|$ times.
Also for a matroid $M = (E, I)$ one can use the ...
- 33
3
votes
1
answer
305
views
Partitioning vertex set to maximize weights of inter-class edges?
An interesting problem has come up in my work, and I haven't quite been able to find references to it so I thought I'd ask here.
Suppose we have some complete, weighted graph with vertex set $V$. Is ...
2
votes
1
answer
155
views
Combinatorial process on multisets of integers
Edit: I prefer to formulate first the problem as Fedor Petrov suggests in the comments:
We are given a multiset $F$, initially containing only the single integer $h$. Sequentially, at each time step, ...
- 1,677
2
votes
1
answer
139
views
Description of Linear Time Algorithm for TSP in Halin Graphs
I am looking for a description of the linear time algorithm for the TSP in Halin graphs, that was given in
"G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling ...
- 13.2k
2
votes
0
answers
33
views
Algorithm for lightest unnested planar vertex-disjoint cycle-cover
Question:
given a finite set $\mathcal{P}$ of disjoint points in the Euclidean plane and the set $\mathcal{C}$ of all simple polygons whose corners are subsets of $\mathcal{P}$,
what is the ...
- 13.2k
2
votes
1
answer
329
views
Worst case performance of heuristic for the non-Eulerian windy postman problem
The windy postman problem seeks the cheapest tour in a complete undirected graph, that traverses each edge at least once; the cost of traversing an edge is positive and may depend on the direction, in ...
- 13.2k
2
votes
0
answers
27
views
Complexity of weighted fractional edge coloring
Given an edge-weighted multigraph $G=(V,E)$ with a positive, rational weight function $(w(e): e \in E)$, the weighted fractional edge coloring problem (WFECP) is to compute ($\min 1^T x$ subject to $...
- 151
1
vote
2
answers
107
views
Minimum edge-weighted directed subgraph in polynomial time
I am looking for an algorithm with polynomial complexity where, given a strongly connected edge-weighted digraph I can find the minimal subgraph which connects some root vertex v to a known set of ...
- 13
1
vote
1
answer
311
views
Tutte's Reduction of Minimum Weight d-Factors to Matching
I am currently interested in minimum weight regular d-spanners (i.e. d-factors) of complete graphs. When searching the internet for related articles, I came across this one, which is concerned with ...
- 13.2k
1
vote
2
answers
256
views
Maximum subgraph edge distance greater than given number
I have a weighted graph G with approximately 75000 nodes. I would like to find subgraph G' induced on a subset of nodes, such that all edge weights in G' are greater than a given constant C and the ...
- 283
1
vote
0
answers
65
views
Find a cut of a graph that minimizes the ratio between the edge weights of the cut and the edge weights inside one subgraph
Given an edge-weighted undirected graph $G=(V,E)$ (can assume the weights are non-negative) and a source node $v_s\in V$, a cut is a partition of $G$'s vertices into two complementary sets $S$ and $T$....
- 143
1
vote
0
answers
168
views
Fastest algorithm to construct a proper edge $(\Delta(G)+1)$-coloring of a simple graph
A proper edge coloring is a coloring of the edges of a graph so that adjacent edges receive distinct colors. Vizing's theorem states that every simple graph $G$ has a proper edge coloring using at ...
- 1,190
1
vote
0
answers
76
views
Generating triangulations with given topology
I am looking for information about the problem of identifying the heaviest minimal subset $F\subset E$ of the edgeset $E$ of a complete symmetric graph $G(V,E)$ with randomly weighted edges such that ...
- 13.2k
1
vote
1
answer
86
views
Complexity of calculating the optimal amalgamation of an optimal cycle-cover
Let $G(V,E)$ be a complete symmetric graph with positive edge weights and let further $\mathcal{C}=\lbrace C_1,\,\cdots\,C_k\rbrace$ be the minimum-weight vertex-disjoint cycle cover.
The set $E$ of ...
- 13.2k
1
vote
0
answers
33
views
Calculating vertex weights via mutually tangent circles of triangles
given a metric graph with positive edge weights $\left|e_{ij}\right|$ a standard task, especially in the context of the Traveling Salesman Problem, is to calculate $\max\sum\limits_{i=1}^n\omega_i:\ \...
- 13.2k
1
vote
0
answers
54
views
Reductions to the MAX-3-DCC Problem
I am currently working on the Max-3-DCC problem that asks for the heaviest vertex-disjoint cycle cover of weighted directed graphs.
The problem has been reduced to 3-SAT in 1979 by L. Valiant in his ...
- 13.2k
1
vote
0
answers
140
views
Is the partition of bipartite graphs NP-hard?
I wonder if the following problem is NP-hard. Is it?
Given a bipartite graph $G = (U, V, E)$ with weights $w : E \to \mathbb{R}_+$, find a partition of $U$ into $U_1, U_2$ and nonempty disjoint ...
- 221
0
votes
1
answer
354
views
Maximize sum of edge weights on spanning tree
Problem: Given a complete graph with n vertices, the edge weight between vertex $i$ and vertex $j$ is $b[i]\times b[j]$.
Under the condition that the degree of point $i$ on spanning tree is DEG $[i]$, ...
- 11
0
votes
0
answers
24
views
Minimizing intersections between spanning trees of graph embeddings in polynomial time
Assume I have $N$ complete graphs $G_1, G_2,...,G_N$, and consider their embeddings $E_1, E_2,...,E_N$ in $\mathbb{R}^2$. Is there a (potentially stochastic) polynomial time algorithm to construct ...
- 1
0
votes
0
answers
16
views
Complexity of finding single source paths with capacity constraints and length constraints
Let $G=(V,A)$ be a directed graph with distinguished vertex $s\in V$ and let $c:A\rightarrow{\mathbb N}$ denote arc capacities. For any $t\in V,t\not=s$ we are given two numbers: $C_{t},L_{t}$. Let $...
- 21
0
votes
2
answers
139
views
Graph vertices selection for paths sum minimalization
Let $G = (V, E)$ be a simple, finite, weighted, undirected, connected graph. Let $P = \{p_{ij}, p_{kl}, p_{il}, ... \}$ be a set of paths, where $p_{ij}$ is a path from $i$-th to $j$-th vertex. Is ...
0
votes
0
answers
36
views
Approximabilty of submodular over modular maximization
Given a non-decreasing, normalized, submodular function $f : 2^{[n]}\mapsto \mathbb{R}_+$ and a modular non-decreasing function $g$, I am wondering what is the best approximation ratio I can hope for ...
- 171
0
votes
1
answer
1k
views
Finding the lowest cost set of disjoint paths using all nodes in a directed graph?
I have a directed graph with edges connecting nodes representing costs.
I wish to find the set of paths which
-go from node 'start' to node 'end'
-are node-disjoint (except for the start and end ...
- 3