Imbalance, Cutwidth, and the Structure of Optimal Orderings

被引：3

作者：

Gorzny, Jan ^{[1
]}

Buss, Jonathan F. ^{[1
]}

机构：

[1] Univ Waterloo, Waterloo, ON, Canada

来源：

COMPUTING AND COMBINATORICS, COCOON 2019 | 2019年 / 11653卷

关键词：

Imbalance; Cutwidth; Twin-cover; Vertex layout; Proper interval graph; Split graph; GRAPHS; RECOGNITION; ALGORITHMS;

D O I：

10.1007/978-3-030-26176-4_18

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We show that both CUTWIDTH and Imbalance are fixed-parameter tractable when parameterized by the twin-cover number of the input graph. We further show that IMBALANCE is NP-complete for split graphs and therefore chordal graphs, but linear-time solvable for proper interval graphs, which equals the complexity of CUTWIDTH on these classes. Both results follow from a new structural theorem, that every instance of CUTWIDTH or IMBALANCE has an optimal ordering of a restricted form.

引用

页码：219 / 231

页数：13

共 30 条

[1]

Bakken O.R., 2018, Master's thesis

[2] Balanced vertex-orderings of graphs [J].

Biedl, T ;

Chan, T ;

Ganjali, Y ;

Hajiaghayi, MT ;

Wood, DR .

DISCRETE APPLIED MATHEMATICS, 2005, 148 (01) :27-48

[3]

Brandstadt A., 1999, GRAPH CLASSES SURVEY, V3

[4] A New Graph Parameter to Measure Linearity [J].

Charbit, Pierre ;

Habib, Michel ;

Mouatadid, Lalla ;

Naserasr, Reza .

COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2017, PT II, 2017, 10628 :154-168

[5] THE LBFS STRUCTURE AND RECOGNITION OF INTERVAL GRAPHS [J].

Corneil, Derek G. ;

Olariu, Stephan ;

Stewart, Lorna .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (04) :1905-1953

[6] A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs [J].

Corneil, DG .

DISCRETE APPLIED MATHEMATICS, 2004, 138 (03) :371-379

[7] On Cutwidth Parameterized by Vertex Cover [J].

Cygan, Marek ;

Lokshtanov, Daniel ;

Pilipczuk, Marcin ;

Pilipczuk, Michal ;

Saurabh, Saket .

ALGORITHMICA, 2014, 68 (04) :940-953

[8]

Fellows MR, 2008, LECT NOTES COMPUT SC, V5369, P294, DOI 10.1007/978-3-540-92182-0_28

[9]

Foldes S., 1977, P 8 S E C COMB GRAPH, P311

[10]

Gajarsky Jakub, 2013, Parameterized and Exact Computation. 8th International Symposium, IPEC 2013. Revised Selected Papers: LNCS 8246, P163, DOI 10.1007/978-3-319-03898-8_15

← 1 2 3 →